遍历序列构造二叉树bintree

遍历序列构造二叉树的方法有多种，下面介绍其中一种常用的方法。

假设已知一棵二叉树的前序遍历序列preorder和中序遍历序列inorder，我们可以通过以下步骤构造出这棵二叉树：

1. 如果preorder和inorder都为空，返回空树；
2. 前序遍历序列的第一个元素是当前子树的根节点；
3. 在中序遍历序列中找到根节点的位置，将inorder分成左子树的中序遍历序列和右子树的中序遍历序列；
4. 根据左子树的中序遍历序列和前序遍历序列，递归构造出左子树；
5. 根据右子树的中序遍历序列和前序遍历序列，递归构造出右子树；
6. 将左子树和右子树连接到根节点上，返回根节点。

具体实现可以参考以下Python代码：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def buildTree(preorder, inorder):
    if not preorder or not inorder:
        return None
    
    # 前序遍历序列的第一个元素是当前子树的根节点
    root_val = preorder[0]
    root = TreeNode(root_val)
    
    # 在中序遍历序列中找到根节点的位置
    inorder_idx = inorder.index(root_val)
    
    # 递归构造左子树和右子树
    root.left = buildTree(preorder[1:inorder_idx+1], inorder[:inorder_idx])
    root.right = buildTree(preorder[inorder_idx+1:], inorder[inorder_idx+1:])
    
    return root

使用示例：

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
root = buildTree(preorder, inorder)

这样就可以根据给定的前序遍历序列和中序遍历序列构造出一棵二叉树了。