Rebuild Tree From Inorder and Postorder
Problem
Given a tree's inorder and postorder traversals (with distinct values), reconstruct the tree.
The last postorder element is always the current root. Find that value's position in the inorder array — left side becomes the left subtree, right side the right subtree. Recurse from the back of postorder, building the right subtree before the left.
Input
inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]Output
level-order: [3, 9, 20, _, _, 15, 7]def build_tree(inorder, postorder):
pos = {v: i for i, v in enumerate(inorder)}
pi = [len(postorder) - 1]
def rec(lo, hi):
if lo > hi: return None
v = postorder[pi[0]]; pi[0] -= 1
node = TreeNode(v)
m = pos[v]
node.right = rec(m + 1, hi)
node.left = rec(lo, m - 1)
return node
return rec(0, len(inorder) - 1)function buildTree(inorder, postorder) {
const pos = new Map();
inorder.forEach((v, i) => pos.set(v, i));
let pi = postorder.length - 1;
function rec(lo, hi) {
if (lo > hi) return null;
const v = postorder[pi--];
const node = { val: v, left: null, right: null };
const m = pos.get(v);
node.right = rec(m + 1, hi);
node.left = rec(lo, m - 1);
return node;
}
return rec(0, inorder.length - 1);
}class Solution {
int pi;
Map<Integer,Integer> pos = new HashMap<>();
int[] post;
public TreeNode buildTree(int[] inorder, int[] postorder) {
post = postorder; pi = postorder.length - 1;
for (int i = 0; i < inorder.length; i++) pos.put(inorder[i], i);
return rec(0, inorder.length - 1);
}
TreeNode rec(int lo, int hi) {
if (lo > hi) return null;
int v = post[pi--];
TreeNode node = new TreeNode(v);
int m = pos.get(v);
node.right = rec(m + 1, hi);
node.left = rec(lo, m - 1);
return node;
}
}int pi;
unordered_map<int,int> pos;
vector<int> post_;
TreeNode* rec(int lo, int hi) {
if (lo > hi) return nullptr;
int v = post_[pi--];
auto node = new TreeNode(v);
int m = pos[v];
node->right = rec(m + 1, hi);
node->left = rec(lo, m - 1);
return node;
}