Given inorder and postorder traversal arrays of the same binary tree, construct and return the tree.
Input: inorder=[9,3,15,20,7], postorder=[9,15,7,20,3] → Output: [3,9,20,null,null,15,7]Input: inorder=[2,1], postorder=[2,1] → Output: [1,2]
The last element of postorder is the root. Find its position in inorder to split into left and right subtrees. Recurse right subtree first (because we consume postorder from end).
- postIdx = postorder.length - 1.
- Find root = postorder[postIdx--] in inorder using HashMap.
- Build right subtree first (inorder[mid+1..hi]), then left (inorder[lo..mid-1]).
import java.util.*;
class Solution {
int postIdx;
Map<Integer, Integer> inMap = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
postIdx = postorder.length - 1;
for (int i = 0; i < inorder.length; i++) inMap.put(inorder[i], i);
return build(postorder, 0, inorder.length - 1);
}
private TreeNode build(int[] postorder, int lo, int hi) {
if (lo > hi) return null;
int rootVal = postorder[postIdx--];
TreeNode root = new TreeNode(rootVal);
int mid = inMap.get(rootVal);
root.right = build(postorder, mid + 1, hi);
root.left = build(postorder, lo, mid - 1);
return root;
}
}
- Time Complexity: O(N)
- Space Complexity: O(N)