Rebuild From In-Order and Post-Order Logs
MediumTrees
Problem
This time the debugger recorded the in-order sequence (left, node, right) and the post-order sequence (left, right, node) of a binary tree with distinct values.
Rebuild the tree from inorder and postorder and return its root.
Example 1
- Input:
- inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]
- Output:
- [3, 9, 20, null, null, 15, 7]
The last post-order value, 3, is the root.
Example 2
- Input:
- inorder = [2, 1], postorder = [2, 1]
- Output:
- [1, 2]
Constraints
- 0 ≤ n ≤ 3000
- Both lists describe the same tree; values are distinct.
- The tree height is at most 500.
Hint
Show the first hint
Where is the root in a post-order list?
Walkthrough
How to approach it
01Clarify before coding
- Distinct values? Yes, so positions in inorder are unique.
- Empty lists? Return an empty tree.
- Same tree in both lists? Yes, guaranteed.
02Brute force
Recursively take the last post-order value as root, scan inorder for it and slice both lists.
Cost: O(n²) time and memory for a chain because of the scans and copies.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.