输入某二叉树的前序遍历和中序遍历的结果 请重建出该二叉树

Question

若已知某二叉树的前序遍历和中序遍历结果，可以通过递归的方式重建该二叉树。

具体步骤如下：

1. 首先，根据前序遍历结果，确定根节点。
2. 然后，根据中序遍历结果，确定左子树和右子树的中序遍历结果。
3. 然后，根据左子树的中序遍历结果，确定左子树的前序遍历结果。
4. 然后，根据右子树的中序遍历结果，确定右子树的前序遍历结果。
5. 最后，根据左子树的前序遍历结果和中序遍历结果，递归重建左子树；根据右子树的前序遍历结果和中序遍历结果，递归重建右子树。

下面是一个示例的实现代码：

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)

    # 在中序遍历中寻找根节点的索引
    root_idx = inorder.index(root_val)

    # 递归重建左子树和右子树
    root.left = buildTree(preorder[1:root_idx+1], inorder[:root_idx])
    root.right = buildTree(preorder[root_idx+1:], inorder[root_idx+1:])

    return root

使用示例：

preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]

root = buildTree(preorder, inorder)

这样，就成功将给定的前序遍历和中序遍历结果重建为对应的二叉树了。