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]