后序遍历最后一个元素必为根节点,据此在中序中定位根并划分左右子树;递归时用闭区间索引传参,终止条件为中序左界大于右界。

后序遍历最后一个元素一定是根节点
这是还原的关键起点。后序遍历顺序是「左子树 → 右子树 → 根」,所以 postorder.back() 就是当前子树的根值。中序遍历中找到这个值的位置,就能把中序序列一分为二:左边是左子树节点,右边是右子树节点。
注意:必须保证中序里存在该值,否则输入非法;若值重复(如多个相同数字),无法唯一还原——C++ 实现时通常假设节点值互异。
递归构建时要正确切分中序和后序子区间
设中序数组为 inorder,后序为 postorder,当前处理范围为:
- 中序区间:
[in_start, in_end](闭区间) - 后序区间:
[post_start, post_end](闭区间)
找到根在中序中的索引 root_idx 后:
- 左子树节点数:
left_size = root_idx - in_start - 左子树在后序中的区间是:
[post_start, post_start + left_size - 1] - 右子树在后序中的区间是:
[post_start + left_size, post_end - 1](注意:最后一位是根,要跳过)
漏掉 -1 或算错 left_size 是最常见越界原因,尤其当左子树为空时(root_idx == in_start),此时 left_size == 0,后序左区间会退化为无效区间,需提前判断终止。
组合式C++代码评审方案,融合静态分析、AI推理、多轮迭代评审和C++专项检查,适用于PR审查、增量代码审查、全项目评审和代码质量评分,触发词包括review cpp、cpp代码评审、C++review、代码审查。
用索引传参比拷贝子数组更安全高效
别写 vector<int>(inorder.begin() + l, inorder.begin() + r)</int> 这种切片——每次递归都分配新内存,既慢又容易搞错边界。直接传原始向量加四个索引参数更可控:
TreeNode* build(vector<int>& inorder, vector<int>& postorder,
int in_l, int in_r, int post_l, int post_r) { ... }</int></int>
初始调用是:build(inorder, postorder, 0, n-1, 0, n-1)。所有边界统一用闭区间,逻辑一致,调试时打印 in_l, in_r, post_l, post_r 能快速定位错在哪一层。
空节点和单节点的边界条件必须显式处理
递归终止条件不是「数组为空」,而是「中序左界大于右界」:if (in_l > in_r) return nullptr;。因为后序可能还剩元素,但中序已无对应位置,说明该分支不存在。
单节点情况(in_l == in_r)会自然落到叶子节点创建逻辑里,无需特殊分支——但如果你在找根索引前没检查 in_l ,就可能触发 <code>std::find 在空区间里搜索,导致未定义行为。
另外,C++ 中用 unordered_map 预存中序值到索引的映射能将每次查找从 O(n) 降到 O(1),但要注意 map 的 key 是值、value 是中序下标,且只建一次,别在递归里反复构造。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!










