LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal (Index Map + Boundary Recursion)
LeetCode 106Binary TreeRecursionHash MapToday we solve LeetCode 106 - Construct Binary Tree from Inorder and Postorder Traversal. The key is to split subtree ranges correctly and build in the right recursive order.
Source: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
English
Problem Summary
Given two integer arrays inorder and postorder for the same binary tree (all values unique), reconstruct and return the tree root.
Core Invariant
In postorder traversal, the last element of a subtree segment is always that subtree's root. Once we know the root in inorder, we can split left and right subtree sizes exactly.
Algorithm
1) Build a hash map: value -> index in inorder for O(1) split lookup.
2) Use a global pointer postIdx starting at postorder.length - 1.
3) Recursive function build(inL, inR) builds subtree from inorder interval [inL, inR].
4) Take rootVal = postorder[postIdx--], create root.
5) Find mid = indexMap.get(rootVal).
6) Build right subtree first using build(mid + 1, inR), then left subtree build(inL, mid - 1).
Why right first? We consume postorder from the end in sequence: root, then right subtree, then left subtree (reverse of left-right-root).
Complexity
Time: O(n).
Space: O(n) (index map + recursion stack in worst case).
Pitfalls
- Building left subtree before right when consuming from postorder end will break ranges.
- Forgetting boundary stop condition inL > inR.
- Repeated linear search in inorder gives O(n^2) worst case; use index map.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
private int postIdx;
private int[] postorder;
private Map<Integer, Integer> index = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.postorder = postorder;
this.postIdx = postorder.length - 1;
for (int i = 0; i < inorder.length; i++) {
index.put(inorder[i], i);
}
return build(0, inorder.length - 1);
}
private TreeNode build(int inL, int inR) {
if (inL > inR) return null;
int rootVal = postorder[postIdx--];
TreeNode root = new TreeNode(rootVal);
int mid = index.get(rootVal);
root.right = build(mid + 1, inR);
root.left = build(inL, mid - 1);
return root;
}
}func buildTree(inorder []int, postorder []int) *TreeNode {
idx := make(map[int]int, len(inorder))
for i, v := range inorder {
idx[v] = i
}
postIdx := len(postorder) - 1
var build func(int, int) *TreeNode
build = func(inL, inR int) *TreeNode {
if inL > inR {
return nil
}
rootVal := postorder[postIdx]
postIdx--
root := &TreeNode{Val: rootVal}
mid := idx[rootVal]
root.Right = build(mid+1, inR)
root.Left = build(inL, mid-1)
return root
}
return build(0, len(inorder)-1)
}class Solution {
public:
unordered_map<int, int> idx;
int postIdx;
TreeNode* build(vector<int>& postorder, int inL, int inR) {
if (inL > inR) return nullptr;
int rootVal = postorder[postIdx--];
TreeNode* root = new TreeNode(rootVal);
int mid = idx[rootVal];
root->right = build(postorder, mid + 1, inR);
root->left = build(postorder, inL, mid - 1);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
for (int i = 0; i < (int)inorder.size(); i++) {
idx[inorder[i]] = i;
}
postIdx = (int)postorder.size() - 1;
return build(postorder, 0, (int)inorder.size() - 1);
}
};class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
index = {v: i for i, v in enumerate(inorder)}
post_idx = len(postorder) - 1
def build(in_l: int, in_r: int) -> Optional[TreeNode]:
nonlocal post_idx
if in_l > in_r:
return None
root_val = postorder[post_idx]
post_idx -= 1
root = TreeNode(root_val)
mid = index[root_val]
root.right = build(mid + 1, in_r)
root.left = build(in_l, mid - 1)
return root
return build(0, len(inorder) - 1)/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val === undefined ? 0 : val)
* this.left = (left === undefined ? null : left)
* this.right = (right === undefined ? null : right)
* }
*/
var buildTree = function(inorder, postorder) {
const idx = new Map();
for (let i = 0; i < inorder.length; i++) {
idx.set(inorder[i], i);
}
let postIdx = postorder.length - 1;
const build = (inL, inR) => {
if (inL > inR) return null;
const rootVal = postorder[postIdx--];
const root = new TreeNode(rootVal);
const mid = idx.get(rootVal);
root.right = build(mid + 1, inR);
root.left = build(inL, mid - 1);
return root;
};
return build(0, inorder.length - 1);
};中文
题目概述
给定同一棵二叉树的 inorder（中序）和 postorder（后序）遍历结果（节点值互不重复），要求重建并返回根节点。
核心不变量
对任意子树区间，后序序列的最后一个元素一定是该子树根节点。找到它在中序中的位置后，左右子树边界就能被唯一确定。
算法步骤
1）先建立哈希表：值 -> 中序下标，便于 O(1) 找切分点。
2）维护全局指针 postIdx，初始为 postorder.length - 1。
3）递归函数 build(inL, inR) 表示构建中序区间 [inL, inR] 的子树。
4）取 postorder[postIdx] 作为根并左移指针。
5）根据根在中序中的位置 mid，切分左右区间。
6）必须先递归构建右子树，再构建左子树。
原因：我们从后序末尾逆向读取，顺序是“根 -> 右 -> 左”，因此递归顺序也必须先右后左。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)（哈希表 + 递归栈最坏情况）。
常见陷阱
- 逆序读取后序时若先建左子树，会导致结构错误。
- 忘记递归终止条件 inL > inR。
- 每次在线性扫描中序找根，会退化到 O(n^2)。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
private int postIdx;
private int[] postorder;
private Map<Integer, Integer> index = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.postorder = postorder;
this.postIdx = postorder.length - 1;
for (int i = 0; i < inorder.length; i++) {
index.put(inorder[i], i);
}
return build(0, inorder.length - 1);
}
private TreeNode build(int inL, int inR) {
if (inL > inR) return null;
int rootVal = postorder[postIdx--];
TreeNode root = new TreeNode(rootVal);
int mid = index.get(rootVal);
root.right = build(mid + 1, inR);
root.left = build(inL, mid - 1);
return root;
}
}func buildTree(inorder []int, postorder []int) *TreeNode {
idx := make(map[int]int, len(inorder))
for i, v := range inorder {
idx[v] = i
}
postIdx := len(postorder) - 1
var build func(int, int) *TreeNode
build = func(inL, inR int) *TreeNode {
if inL > inR {
return nil
}
rootVal := postorder[postIdx]
postIdx--
root := &TreeNode{Val: rootVal}
mid := idx[rootVal]
root.Right = build(mid+1, inR)
root.Left = build(inL, mid-1)
return root
}
return build(0, len(inorder)-1)
}class Solution {
public:
unordered_map<int, int> idx;
int postIdx;
TreeNode* build(vector<int>& postorder, int inL, int inR) {
if (inL > inR) return nullptr;
int rootVal = postorder[postIdx--];
TreeNode* root = new TreeNode(rootVal);
int mid = idx[rootVal];
root->right = build(postorder, mid + 1, inR);
root->left = build(postorder, inL, mid - 1);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
for (int i = 0; i < (int)inorder.size(); i++) {
idx[inorder[i]] = i;
}
postIdx = (int)postorder.size() - 1;
return build(postorder, 0, (int)inorder.size() - 1);
}
};class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
index = {v: i for i, v in enumerate(inorder)}
post_idx = len(postorder) - 1
def build(in_l: int, in_r: int) -> Optional[TreeNode]:
nonlocal post_idx
if in_l > in_r:
return None
root_val = postorder[post_idx]
post_idx -= 1
root = TreeNode(root_val)
mid = index[root_val]
root.right = build(mid + 1, in_r)
root.left = build(in_l, mid - 1)
return root
return build(0, len(inorder) - 1)/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val === undefined ? 0 : val)
* this.left = (left === undefined ? null : left)
* this.right = (right === undefined ? null : right)
* }
*/
var buildTree = function(inorder, postorder) {
const idx = new Map();
for (let i = 0; i < inorder.length; i++) {
idx.set(inorder[i], i);
}
let postIdx = postorder.length - 1;
const build = (inL, inR) => {
if (inL > inR) return null;
const rootVal = postorder[postIdx--];
const root = new TreeNode(rootVal);
const mid = idx.get(rootVal);
root.right = build(mid + 1, inR);
root.left = build(inL, mid - 1);
return root;
};
return build(0, inorder.length - 1);
};
Comments