输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出：
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
限制：
0 <= 节点个数 <= 5000
解
通过前序遍历确定根节点，再通过中序遍历确定左右子树，递归上述过程即可得出树的结构。
比如，当递归到最后一层时，如何确定最树结构？
preorder = [20, 15, 7]
inorder = [15, 20, 7]
- 根据 preorder 获得根节点：
root = preorder[0] - 在 inorder 中找到 root 的位置：
index = 1 - 利用 index ，在 inorder 中确定左子树和右子树数量：
left_number = 1, right_number = 1以及子树的 inorder 。 - 利用子树数量，从 preorder 中确定子树的 preorder 。
得到左右子树的 preordr 和 inorder 后，继续上述步骤，以左子树为例：
preorder = [15]
inorder = [15]
- 根据 preorder 获得根节点：
root = preorder[0] = 15 - 在 inorder 中找到 root 的位置：
index = 0 - 利用 index ，在 inorder 中确定左子树和右子树数量：
left_number = 0, right_number = 0以及子树的 inorder - 利用子树数量，从 preorder 中确定子树的 preorder 。
- 发现 preorder 为空，返回 None
- 到此确定左子树是 15 。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder or not inorder:
return None
index = self.find_index(preorder, inorder)
root = TreeNode(preorder[0])
root.left = self.buildTree(preorder[1: index + 1], inorder[0: index])
root.right = self.buildTree(preorder[index + 1: ], inorder[index + 1:])
# 1. 当子树的 preorder 或者 inorder 为空时，第一个子树构建完毕
# 2. 当第一个子树构建完毕时，第二个子树构建完毕...
return root
def find_index(self, preorder, inorder):
"""
寻找中序遍历中根节点的位置
"""
for index, value in enumerate(inorder):
if value == preorder[0]:
return index