You are given two integer arrays: preorder, the preorder traversal of a binary tree, and inorder, the inorder traversal of the same tree. All values are unique. Rebuild the tree and return its root.
- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- All values are unique and both arrays describe the same tree
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The root is preorder[0]. In inorder, everything before the root belongs to the left subtree and everything after it to the right subtree, so we can split and recurse. Done naively, finding the root in inorder is a linear scan and slicing copies arrays, which adds up to O(n^2). Two improvements make it O(n): a hash map from value to inorder index finds the split in O(1), and a single moving pointer into preorder (left subtree first, then right) hands out roots in the right order without slicing.
Algorithm
- Build
pos[value] = index in inorder. Set a pointerpre = 0. - Define
build(lo, hi)for the inorder rangelo..hi. Iflo > hi, return null. - Take
val = preorder[pre], increasepre, and create the node. - Let
mid = pos[val]. Build the left child from(lo, mid - 1)first, then the right child from(mid + 1, hi). - Return
build(0, n - 1).
O(n)Space: O(n) for the map and recursionclass Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: pos = {v: i for i, v in enumerate(inorder)} # value -> index in inorder pre = 0 # next root in preorderΒ def build(lo, hi): nonlocal pre if lo > hi: return None val = preorder[pre] pre += 1 node = TreeNode(val) mid = pos[val] node.left = build(lo, mid - 1) # left first: matches preorder node.right = build(mid + 1, hi) return nodeΒ return build(0, len(inorder) - 1)