478. Rebuild From In and Post
An archaeologist has two lists describing the rooms of a lost temple that is shaped like a binary tree. The list inorder names the rooms of the left wing, then the room itself, then the rooms of the right wing, applied at every room. The list postorder names the rooms of the left wing, then the rooms of the right wing, and the room itself last, again at every room. Every room has a different number.
Given inorder and postorder, which are guaranteed to be the two traversals of one and the same binary tree, reconstruct that tree and return its root. The arrays have equal length of at least 1.
Example 1
- Input:
- inorder = [5,2,-8,9,12,16], postorder = [2,5,9,16,12,-8]
- Output:
- [-8,5,12,null,2,9,16]
- Explanation:
The last postorder 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:
- inorder = [20,10,30], postorder = [20,10,30]
- Output:
- [30,10,null,20]
- Explanation:
The last postorder value is the root; splitting the inorder list around it recursively gives the tree [30,10,null,20] in level order.
Example 3
- Input:
- inorder = [0,1,2,3,4,5,6,8]postorder = [0,2,3,1,5,8,6,4]
- Output:
- [4,1,6,0,3,5,8,null,null,2]
- Explanation:
The last postorder 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 ≤ inorder.length == postorder.length ≤ 5000
-104 ≤ inorder[i], postorder[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)