Python从前序与中序遍历序列构造二叉树_构造一棵二叉排序树并给出构造过程,python

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7
链接：https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xoei3r/
来源：力扣（LeetCode）
 

 
# 和上面的根据中序、后序序列构建二叉树类似，只是root的生成位置由后序最后一个元素改为前序第一个元素；
# 暴躁老哥在线刷题 思路：
# 首先根据前序遍历的定义可以知道，preorder这个数组的第一个元素preorder[0]一定是root，
# 再根据中序遍历的定义， 在inorder这个数组里，root前面的元素都属于root的左子树，root后面的元素都属于右子树，
# 从这一步得到了left_inorder和right_inorder，
# 接下来我们只需要把root在inorder里的位置index = inorder.index(preorder[0])查找出来，就可以知道其左子树和右子树的长度，
# 然后再回到preorder，root后面先是左子树，然后是右子树，因为上一步我们已经知道了它们的长度，所以可以得到left_preorder和left_preorder，
# 然后递归不就完事了。
# ————————————————
# 版权声明&#