The problem
Two ways to list a tree’s values: preorder (a node, then its left subtree, then its right) and inorder (the left subtree, then the node, then the right).
Given both lists for the same tree, whose values are all different, build the tree and return its root.
Examples
- Input
preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
- Output
[3, 9, 20, null, null, 15, 7]
- Input
preorder = [-1], inorder = [-1]
- Output
[-1]
Constraints
- 1 ≤ preorder.length ≤ 3000
inorderhas the same length.- −3000 ≤ value ≤ 3000, all different
- Both lists come from the same tree.
The idea
Preorder puts a root first. Inorder puts that root between its two subtrees: everything before it in inorder is on the left, everything after on the right. So the first preorder value splits inorder into the two subtrees, and the same holds inside each.
Build recursively over a range of inorder. Take the next preorder value as the root, look up where it sits in inorder (a hash map makes that one step), build the left part, then the right part. Preorder lists the left subtree entirely before the right, so reading preorder straight through hands every call its root in turn.
- Time
- O(n) — each value placed once
- Space
- O(n) — the map
Solution · every language run against every case
class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: where = {v: i for i, v in enumerate(inorder)} # each value's place in inorder nxt = 0 # the next preorder value: the root of the next subtree to build def build(lo, hi): # the subtree made of inorder[lo:hi] nonlocal nxt if lo >= hi: return None root = TreeNode(preorder[nxt]) nxt += 1 m = where[root.val] # left of it in inorder is the left subtree, right of it the right root.left = build(lo, m) root.right = build(m + 1, hi) return root return build(0, len(inorder))