LeetCode_105_从前序与中序遍历序列构造二叉树_hn LeetCode_105_从前序与中序遍历序

题目描述根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

3 / \ 920 /\ 157

解答方法方法一：递归思路
先来了解一下前序遍历和中序遍历是什么。
前序遍历：遍历顺序为父节点 -> 左子节点 -> 右子节点
后续遍历：遍历顺序为左子节点 -> 父节点 -> 右子节点
我们可以发现：前序遍历的第一个元素为根节点，而在后序遍历中，该根节点所在位置的左侧为左子树，右侧为右子树。
例如在例题中：
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
【LeetCode_105_从前序与中序遍历序列构造二叉树_hn】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

时间复杂度空间复杂度提交结果