递归与二叉树
由遍历序列反推二叉树
反过来的问题
前中后序那三个时刻讲的是「给一棵树，怎么走出序列」。 这一篇反过来：给你序列，把树还原出来。
它值得单独一篇，是因为解法依赖一个不显然的观察：
前序和后序负责「指认根」，中序负责「分开左右」。 两个职责缺一不可 —— 这也是下面那个「前序 + 后序反而不行」的原因。
前序 + 中序
前序是「根左右」，所以第一项一定是根。 拿这个根去中序里找位置，它左边的全是左子树、右边的全是右子树：
前序 [3 | 9 | 20 15 7] 3 是根
中序 [9 | 3 | 15 20 7] 3 左边 [9] 是左子树，右边 [15,20,7] 是右子树function buildPreIn(preorder, inorder) {
const pos = new Map();
inorder.forEach((v, i) => pos.set(v, i)); // 值 → 中序下标，把「找根」降到 O(1)
let p = 0; // 前序游标，全局只走一遍
function build(lo, hi) { // 负责中序区间 [lo, hi]
if (lo > hi) return null;
const val = preorder[p++]; // 前序当前项就是这棵子树的根
const node = { val, left: null, right: null };
const i = pos.get(val);
node.left = build(lo, i - 1); // ⚠️ 必须先左后右
node.right = build(i + 1, hi);
return node;
}
return build(0, inorder.length - 1);
}⭐ 这里有个容易被忽略的设计：前序游标 p 是全局的，只往前走，从不回退。
每层递归只管「我负责中序的哪一段」，根是谁由 p 自动给出。
不需要同时切两个数组的区间 —— 那种写法要维护四个下标，边界错的概率高得多。
🚨 build(lo, i-1) 必须写在 build(i+1, hi) 前面。
因为前序是「根左右」，p 接下来要吐出的是左子树的根。
两行调换位置，p 就把右子树的根发给了左子树。
中序 + 后序：顺序要反过来
后序是「左右根」，所以最后一项是根，倒着读。 但倒着读的序列是「根右左」—— 所以递归时必须先建右子树：
function buildInPost(inorder, postorder) {
const pos = new Map();
inorder.forEach((v, i) => pos.set(v, i));
let p = postorder.length - 1; // 从末尾往前
function build(lo, hi) {
if (lo > hi) return null;
const val = postorder[p--];
const node = { val, left: null, right: null };
const i = pos.get(val);
node.right = build(i + 1, hi); // 🚨 先右
node.left = build(lo, i - 1); // 后左
return node;
}
return build(0, inorder.length - 1);
}🚨 写成「先左后右」的症状：不是答案错，是爆栈
这个错很值得说，因为它的表现和你预期的不一样。
顺序反了之后，p 吐出的「根」并不属于当前这段中序区间，
于是 pos.get(val) 给回一个落在 [lo, hi] 之外的下标。
区间不再收缩，递归下不去底：
输入 中序 [9,3,15,20,7] / 后序 [9,15,7,20,3]
正确：[3,9,20,null,null,15,7]
反了：💥 RangeError: Maximum call stack size exceeded⭐ 这个错的行为可以精确刻画，不用报百分比。穷举 n=1~11 的全部 82499 种树形， 逐棵比对：
错版崩溃 ⟺ 树中存在【某个节点有两个孩子】
错版侥幸正确 ⟺ 树是一条链（每个节点至多一个孩子），恰好 2^(n-1) 棵
答案错 0 棵（所有 n 上都是 0）⭐ 于是出错率有闭式解：1 − 2^(n-1) / Catalan(n)。
n 树形数 其中是链 出错率
1 1 1 0%
2 2 2 0% ← 两个节点以内，这个 bug 测不出来
3 5 4 20.00% ← 最小能暴露它的规模
5 42 16 61.90%
10 16,796 512 96.95%
20 6,564,120,420 524,288 99.99%🚨 所以「崩溃很吵、一跑就知道」有个前提：你的用例不能是链。
n ≤ 2 时全部树形都是链，必然测不出；n = 3 的 5 种形状里也只有 1 种能暴露。
👉 判据：测这类「左右搞反」的 bug，用例必须含一个有两个孩子的节点。
⭐ 顺带：前序版写成「先右后左」的刻画完全相同（同样穷举验过）， 正文这一节讲的是后序版，但两边是一回事。
📌 真正需要警惕的是那些「不崩、只是悄悄算错」的 bug —— 比如摩尔投票在没有众数时照样返回一个像样的值。 同样是写错，症状的响亮程度差别很大，而响亮的那种其实更容易对付。
⭐ 为什么前序 + 后序反而不够
这是这道题最值得想清楚的地方。前序和中序行、中序和后序行， 前序和后序却不行 —— 直觉上信息量明明一样多。
原因在开头那句：前序和后序都只会「指认根」，谁都不能分开左右。
最小反例只要两个节点：
树A: 1 树B: 1
/ \
2 2
前序 [1, 2] [1, 2] ← 一样
后序 [2, 1] [2, 1] ← 一样
中序 [2, 1] [1, 2] ← 只有它能分开📌 判据很干净：当某个节点只有一个孩子时，前序 + 后序分不出它是左孩子还是右孩子。
⭐ 这条判据穷举证明过，不是观察。把「形状 × 值的全排列」全部列出来
（n=7 时 2162160 棵带标号树），按 (前序, 后序) 分组：
n 带标号树数 分组数 落在多树组里的 有单孩子节点的
3 30 12 24 24 ✅ 逐棵一致
5 5,040 1,080 4,800 4,800 ✅
7 2,162,160 257,040 2,136,960 2,136,960 ✅「有歧义」与「有单孩子节点」在 n=1~7 上是同一批树，一棵不差。
🚨 而歧义比例这件事，一半可以直接算出来，不用测。 满二叉树（每节点 0 或 2 个孩子）的节点数必为奇数 —— 所以偶数个节点的树必然有单孩子节点，歧义率恒为 100%，这是定理不是实测：
n 全部树形数 其中满二叉树
2 2 0 ← 偶数一律 0
4 14 0
10 16,796 0
11 58,786 42
21 24,466,267,020 16,796⚠️ 所以真正需要采样的是奇数 n。实测 20 万棵随机树：
n 1 3 5 9 11 19 21 49/51
有歧义 0% 66.66% 86.56% 97.87% 99.07% 99.98% 99.99% 100.00%⭐ 十个节点往上，奇数规模也基本必然有歧义（n=11 已经 99.07%）—— 结论成立，但支撑它的必须是奇数那几档。
📌 反过来也验证了：限定成满二叉树之后歧义就消失了 ——
采样 78001 棵满二叉树，(前序,后序) 相同却形状不同的有 0 棵。
⭐ 所以力扣 #889 从前序与后序遍历序列构造二叉树（中等） 的题面原话是「如果存在多个答案，您可以返回其中任何一个」， 而不是「返回那棵树」—— 题面里这种措辞的松紧，往往正对应着一个可以证明的结论。
那张哈希表值不值：看数据形状
pos 那张「值 → 中序下标」的表，是为了把「在中序里找根」从 O(n) 降到 O(1)。
去掉它改用线性扫描，理论上是 O(n) → O(n²)。
🚨 但「线性扫描」有两种自然写法，「链状」也有两个方向， 而这两个选择各自都能让结论翻转。 先看扫描步数（与机器无关，可精确计算）：
写法 形状 n=2000 n=4000 涨幅 闭式解
区间内从 lo 扫 右链 2,000 4,000 2.0× n
区间内从 lo 扫 左链 2,001,000 8,002,000 4.0× n(n+1)/2
区间内从 lo 扫 平衡 10,870 23,734 2.2× ≈ n·log₂n / 2
整数组 indexOf 任何形状 2,001,000 8,002,000 4.0× n(n+1)/2（与形状无关）⚠️ indexOf 那一行是关键：它对任何形状都是 n(n+1)/2 ——
因为查一个值的代价就是它在数组里的下标，把 n 个根加起来恒等于 n(n+1)/2。
用这种写法，平衡树也是 O(n²)。
于是耗时（各预热 5 次、15 次取中位数）分成两种局面：
写法 形状 n=2000 n=4000 线性版/哈希版
区间内从 lo 扫 左链 12.6× 18.8× ← O(n²)，倍数随 n 涨
区间内从 lo 扫 右链 0.3× 0.3× ← 线性版反而快 3 倍
区间内从 lo 扫 平衡 0.4× 0.3× ← 线性版更快
整数组 indexOf 平衡 11.1× 20.2× ← 换个写法，平衡树也变慢 20 倍⭐ 所以两条结论都要带上口径：
- 「链状是最坏情况」只对左链成立。 右链下每段子树的根恰好就在区间左端， 一步命中，线性版反而比哈希版快 3 倍。「链状」这个词不够，得说清方向。
- 「平衡树上线性扫描反而快」只在「区间内从 lo 扫」这个写法下成立。
因为那时每层要扫的区间只有该子树那么长，总量 ≈
n·log₂n/2且常数极小； 而哈希表要先花 O(n) 建表、每次查询还有哈希开销。
📌 和单调栈那篇得到的是同一个结论： 看到「优化成 O(n)」先问「在什么数据上」。 哈希表在这里买的不是平均速度， 是消掉最坏情况 —— 而判题机的数据正是照着最坏情况构造的。 ⭐ 再加一条：也要问「拿什么跟它比」。 同一个「线性扫描」的两种写法， 一个在平衡树上快、一个慢二十倍。
一类更大的题：序列化与反序列化
把树变成字符串、再变回来，是同一件事的一般形式。 关键在于空节点也要记下来 —— 否则就回到上面那个「分不出左右」的困境：
前序 + 空节点占位: [1, 2, #, #, #] ← 树A（2 是左孩子）
[1, #, 2, #, #] ← 树B（2 是右孩子）⭐ 补上 # 之后，单独一个前序就够了，不再需要中序 ——
因为「空」这个信息本身就把左右分开了。这正是 #297 的标准解法。
这一篇的判据
| 给了什么 | 能不能唯一还原 | 为什么 |
|---|---|---|
| 前序 + 中序 | ✅ | 前序指根，中序分左右 |
| 中序 + 后序 | ✅ | 后序指根（倒读），中序分左右 |
| 前序 + 后序 | ❌ | 两个都只能指根，没人分左右 |
| 前序 + 空节点占位 | ✅ | 「空」本身就分开了左右 |
| 前序（且是 BST） | ✅ | BST 的中序天然有序，等于白送一个中序 |
🚨 三个高频错误：
- 后序版忘了先右后左 —— 症状是爆栈，不是答案错
- 两边都切区间 —— 维护四个下标，边界几乎必错；用「全局游标 + 只切中序区间」
- 假设值不重复 ——
pos表用值当 key，有重复值时会互相覆盖。 ⚠️ 力扣这几道题明确保证节点值互不相同（#105 的提示原话是 「preorder 和 inorder 均 无重复 元素」），所以能这么写。 和最近公共祖先、 摩尔投票一样，这又是一处「解法在利用题面给的前提」—— 看到「题目保证……」就该想想自己有没有正在依赖它。
练习
勾选记录做过哪些，0 / 7 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。
- 105. 从前序与中序遍历序列构造二叉树中等⭐ 本篇主讲。全局前序游标 + 只切中序区间，别两边都切
- 106. 从中序与后序遍历序列构造二叉树中等🚨 后序倒读是「根右左」，必须先建右子树；写反了 68% 的输入会爆栈而不是答案错
- 889. 从前序与后序遍历序列构造二叉树中等⭐ 题面说「返回任一」而不是「返回那棵」—— 因为单孩子节点分不出左右，n≥10 的随机树 100% 有歧义
- 108. 将有序数组转换为二叉搜索树简单有序数组就是 BST 的中序；取中点当根即平衡
- 1008. 前序遍历构造二叉搜索树中等BST 只给前序也够 —— 它的中序天然有序，等于白送一个中序
- 654. 最大二叉树中等换个「谁是根」的规则：区间最大值当根。骨架完全一样
- 297. 二叉树的序列化与反序列化困难⭐ 一般形式。补上空节点占位后，单独一个前序就够了，不再需要中序
⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。