题目描述
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
解答方法
方法一：递归
思路
先来了解一下前序遍历和中序遍历是什么。
前序遍历：遍历顺序为 父节点 -> 左子节点 -> 右子节点
后续遍历：遍历顺序为 左子节点 -> 父节点 -> 右子节点
我们可以发现：前序遍历的第一个元素为根节点，而在后序遍历中，该根节点所在位置的左侧为左子树，右侧为右子树。
例如在例题中：
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
preorder 的第一个元素 3 是整棵树的根节点。inorder 中 3 的左侧 [9] 是树的左子树，右侧 [15, 20, 7] 构成了树的右子树。
所以构建二叉树的问题本质上就是：
1、找到各个子树的根节点 root
2、构建该根节点的左子树
3、构建该根节点的右子树
代码
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if len(preorder) == 0:
return None
# 前序遍历第一个值为根节点
root = TreeNode(preorder[0])
# 因为没有重复元素，所以可以直接根据值来查找根节点在中序遍历中的位置
i = inorder.index(preorder[0])
# 构建左子树
root.left = self.buildTree(preorder[1:i+1], inorder[:i])
# 构建右子树
root.right = self.buildTree(preorder[i+1:], inorder[i+1:])
return root
