105. Construct Binary Tree from Preorder and Inorder Traversal 从前序与中序遍历序列构造二叉树
难度: 中等
刷题内容
原题连接
- https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
- https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
内容描述
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
解题方案
思路 1
一句话，看到树🌲就要想到递归
- preorder 是 根 -> 左 -> 右
- inorder 是 左 -> 根 -> 右
首先pre的第一个就是整个树的root, 假设 preorder[0] = inorder[k],那么inorder的前k-1个就是树的左子树，后面部分就是树的右子树
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if not preorder or len(preorder) == 0:
return None
root = TreeNode(preorder[0])
k = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1:k+1], inorder[0:k])
root.right = self.buildTree(preorder[k+1:], inorder[k+1:])
return root
