#106
Construct Binary Tree from Inorder and Postorder Traversal
Medium Divide by root position
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Rebuild a binary tree (with unique values) from its inorder and postorder traversals.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: rebuild from inorder and postorder.
Why this works: postorder's last value is the root. Read postorder backwards: root, then the right subtree, then the left.
Example: in [9, 3, 15, 20, 7], post [9, 15, 7, 20, 3]
root 3 → build right from 20 (left 15, right 7) → then left 9✦Hints open one at a time
The last postorder value is the root.
Read postorder from the back: root, then the right subtree, then the left.
↗Approach
Pointer starts at the end of postorder. build(lo, hi): take postorder[ptr--] as root, find its inorder index m, build the RIGHT subtree first (m + 1, hi), then left (lo, m − 1).
</>Solution (Java)
import java.util.*;
/**
* class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; } } // provided by LeetCode
*/
class Solution {
private int post;
private int[] postorder;
private final Map<Integer, Integer> pos = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.postorder = postorder;
post = postorder.length - 1;
for (int i = 0; i < inorder.length; i++) pos.put(inorder[i], i);
return build(0, inorder.length - 1);
}
private TreeNode build(int lo, int hi) {
if (lo > hi) return null;
TreeNode root = new TreeNode(postorder[post--]);
int m = pos.get(root.val);
root.right = build(m + 1, hi); // right first when reading backwards
root.left = build(lo, m - 1);
return root;
}
}!Common mistake
Building left before right while reading postorder backwards.
Complexity
- Time: O(n).
- Space: O(n).
Topic: Binary Trees
🎬 Episodes 53–60: video coming soon