[LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal_Medium tag: Tree Traversal

时间:2024-10-03 13:35:02

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

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

Return the following binary tree:

    3
/ \
9 20
/ \
15 7 这个题目的思路就是利用preorder 和inorder的两种特性, 我们可以发现, preorder[0] 总是root, 然后inorder 里面根据之前的root, 可以将inorder分为left tree和right tree,
然后return root, recursive call即可. 1. Constraints
1) pre or in can be empty 2. ideas
recursively DFS, 分别得到root, root.left & root.right, 返回root 3. Code
class Solution:
def constructBT(self, preorder, inorder):
if not preorder or not inorder: return #note 别忘了not before inorder
root, index = TreeNode(preorder[0]), inorder.index(preorder[0])
root.left = self.constructBT(preorder[1:1+index], inorder[:index])
root.right = self.constructBT(preorder[1+index:], inorder[index+1:])
return root

4. Test cases

1) edge case

2)

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