Rebuild Tree From Preorder and Inorder
Problem
Given a tree's preorder and inorder traversals (with distinct values), reconstruct the tree.
The first preorder element is always the current root. Find that value's position in the inorder array — everything to its left forms the left subtree, everything to its right forms the right subtree. Recurse with the matching slices of preorder.
Input
preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]Output
level-order: [3, 9, 20, _, _, 15, 7]def build_tree(preorder, inorder):
pos = {v: i for i, v in enumerate(inorder)}
pi = [0]
def rec(lo, hi):
if lo > hi: return None
v = preorder[pi[0]]; pi[0] += 1
node = TreeNode(v)
m = pos[v]
node.left = rec(lo, m - 1)
node.right = rec(m + 1, hi)
return node
return rec(0, len(inorder) - 1)function buildTree(preorder, inorder) {
const pos = new Map();
inorder.forEach((v, i) => pos.set(v, i));
let pi = 0;
function rec(lo, hi) {
if (lo > hi) return null;
const v = preorder[pi++];
const node = { val: v, left: null, right: null };
const m = pos.get(v);
node.left = rec(lo, m - 1);
node.right = rec(m + 1, hi);
return node;
}
return rec(0, inorder.length - 1);
}class Solution {
int pi = 0;
Map<Integer, Integer> pos = new HashMap<>();
int[] pre;
public TreeNode buildTree(int[] preorder, int[] inorder) {
pre = preorder;
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 = pre[pi++];
TreeNode node = new TreeNode(v);
int m = pos.get(v);
node.left = rec(lo, m - 1);
node.right = rec(m + 1, hi);
return node;
}
}int pi = 0;
unordered_map<int,int> pos;
vector<int> pre_;
TreeNode* rec(int lo, int hi) {
if (lo > hi) return nullptr;
int v = pre_[pi++];
auto node = new TreeNode(v);
int m = pos[v];
node->left = rec(lo, m - 1);
node->right = rec(m + 1, hi);
return node;
}