Construct Binary Tree from Preorder and Inorder Traversal
Construct Binary Tree from Preorder and Inorder Traversal is a medium Trees problem from the Blind 75. The key pattern is divide and conquer, and a good solution runs in O(n) time.
Problem
Reconstruct the unique tree and print its trimmed level-order representation.
Examples
Example 1
Input
{"preorder":[3,9,20,15,7],"inorder":[9,3,15,20,7]}Output
[3,9,20,null,null,15,7]Example 2
Input
{"preorder":[-1],"inorder":[-1]}Output
[-1]Example 3
Input
{"preorder":[1,2,3],"inorder":[3,2,1]}Output
[1,2,null,3]Approach
The next preorder value is the root of the current subtree; its position in the inorder list splits left from right. An index map makes each split O(1).
| Pattern | Divide and conquer |
|---|---|
| Time | O(n) |
| Space | O(n) |
Watch out for
Values are distinct, which is what makes the index map unambiguous.