477. Rebuild From Pre and In
Two surveyors walked through the same binary-tree shaped cave system and each wrote down the chamber numbers in the order they met them. The first surveyor recorded preorder: every chamber, then everything in its left tunnel, then everything in its right tunnel. The second recorded inorder: everything in the left tunnel, then the chamber, then everything in the right tunnel. All chamber numbers are different.
Rebuild the cave system. Given preorder and inorder, which are guaranteed to come from one and the same binary tree, construct that tree and return its root. Both arrays have the same length, which is at least 1.
Example 1
- Input:
- preorder = [-8,5,2,12,9,16], inorder = [5,2,-8,9,12,16]
- Output:
- [-8,5,12,null,2,9,16]
- Explanation:
The first preorder value is the root; splitting the inorder list around it recursively gives the tree [-8,5,12,null,2,9,16] in level order.
Example 2
- Input:
- preorder = [30,10,20], inorder = [20,10,30]
- Output:
- [30,10,null,20]
- Explanation:
The first preorder value is the root; splitting the inorder list around it recursively gives the tree [30,10,null,20] in level order.
Example 3
- Input:
- preorder = [4,1,0,3,2,6,5,8]inorder = [0,1,2,3,4,5,6,8]
- Output:
- [4,1,6,0,3,5,8,null,null,2]
- Explanation:
The first preorder value is the root; splitting the inorder list around it recursively gives the tree [4,1,6,0,3,5,8,null,null,2] in level order.
Constraints
1 ≤ preorder.length == inorder.length ≤ 5000
-104 ≤ preorder[i], inorder[i] ≤ 104
All values are distinct and both arrays describe the same tree.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)