图 1：本文封面，两条序列如何合成一棵树。
先说明属性：这是一篇历史笔试题复盘，题目出自本地历史笔试资料，与任何公司的当前招聘无关。题面很经典：给定一棵二叉树的前序遍历和中序遍历序列，把树还原出来。考点不在「会不会」，而在「分治点找得准不准」。
第一步，想清楚两个序列各自提供了什么信息。
前序遍历的顺序是根、左、右——它的第一个元素一定是整棵树的根。中序遍历的顺序是左、根、右——一旦知道根是谁，根左边的所有元素构成左子树，右边的构成右子树。一个给「谁是根」，一个给「谁归哪边」，两条信息正好互补，这就是能还原的根本原因。
这里藏着一个唯一性前提：序列里不能有重复值。如果两个节点值相同，「根在中序里的位置」就有歧义，同一对序列可能对应多棵树。所以题面默认节点值互不相同，答题时主动点出这个前提，是加分项。
第二步，把分治点写成下标运算。
递归的主轴只有三句话：取前序当前区间的首元素作为根；在中序当前区间里定位这个根，得到下标 k，k 左边是左子树、右边是右子树；左子树的大小是 k 减去中序左边界，按这个大小把前序区间也切成左右两段，分别递归。
关键细节在前序的切分：前序区间里紧跟根的一段，长度恰好等于左子树大小，这段是左子树的前序，剩下的是右子树的前序。分治点说到底就一个——根在中序中的下标，其余边界都由它推算出来。
第三步，写出可运行代码并实测。
朴素写法每次在中序里线性查找根，最坏 O(n²)；建一个「值到下标」的哈希表，每次 O(1) 定位，整体降到 O(n)。下面这份实现用 Node.js 22.15.0 直接运行（node buildtree.js）即可，内置三组用例：题面小例、200 节点随机树往返校验、不自洽输入拦截：
'use strict';
// 由前序 + 中序遍历还原二叉树：分治点 = 根在中序中的下标
function buildTree(preorder, inorder) {
if (preorder.length !== inorder.length) throw new RangeError('两个序列长度必须一致');
const pos = new Map(inorder.map((v, i) => [v, i])); // 值 -> 中序下标
const build = (pl, pr, il, ir) => {
if (pl > pr) return null; // 空区间：没有节点
const rootVal = preorder[pl]; // 前序首元素就是当前子树的根
const k = pos.get(rootVal);
if (k === undefined || k < il || k > ir) throw new Error('序列不自洽，无法还原');
const leftSize = k - il; // 中序里根左边的元素数 = 左子树大小
return {
val: rootVal,
left: build(pl + 1, pl + leftSize, il, k - 1), // 前序紧跟根的一段是左子树
right: build(pl + leftSize + 1, pr, k + 1, ir), // 剩下的是右子树
};
};
return build(0, preorder.length - 1, 0, inorder.length - 1);
}
function toPreorder(root, out = []) {
if (root) { out.push(root.val); toPreorder(root.left, out); toPreorder(root.right, out); }
return out;
}
function toInorder(root, out = []) {
if (root) { toInorder(root.left, out); out.push(root.val); toInorder(root.right, out); }
return out;
}
// 用例 1：题面小例
const pre1 = ['A', 'B', 'D', 'C'];
const in1 = ['D', 'B', 'A', 'C'];
const t1 = buildTree(pre1, in1);
console.log(`还原后前序 [${toPreorder(t1)}] 与原前序一致：${JSON.stringify(toPreorder(t1)) === JSON.stringify(pre1)}`);
console.log(`还原后中序 [${toInorder(t1)}] 与原中序一致：${JSON.stringify(toInorder(t1)) === JSON.stringify(in1)}`);
// 用例 2：随机 200 节点树，往返校验
function randomTree(size) {
const vals = Array.from({ length: size }, (_, i) => i);
for (let i = vals.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[vals[i], vals[j]] = [vals[j], vals[i]];
}
let root = null;
const insert = (node, v) => {
if (!node) return { val: v, left: null, right: null };
if (v < node.val) node.left = insert(node.left, v);
else node.right = insert(node.right, v);
return node;
};
for (const v of vals) root = insert(root, v);
return root;
}
const big = randomTree(200);
const pre2 = toPreorder(big);
const in2 = toInorder(big);
const rebuilt = buildTree(pre2, in2);
console.log(`200 节点随机树往返校验：${JSON.stringify(toPreorder(rebuilt)) === JSON.stringify(pre2) && JSON.stringify(toInorder(rebuilt)) === JSON.stringify(in2)}`);
// 用例 3：不自洽输入（中序里不存在前序的根）
try {
buildTree(['A', 'B'], ['A', 'C']);
} catch (e) {
console.log(`不自洽输入：${e.message}`);
}
实测输出：
还原后前序 [A,B,D,C] 与原前序一致：true
还原后中序 [D,B,A,C] 与原中序一致：true
200 节点随机树往返校验：true
不自洽输入：序列不自洽，无法还原
往返校验是最有说服力的自证：随机生成一棵树，序列化成前序和中序，再还原回来，两条序列与原始输出逐位一致——还原的树与原树同构。
图 2：分治三步走——前序定根、中序切边、按大小分前序。
可能的追问。
「前序加后序能不能还原？」不能唯一还原：后序只能告诉你根（最后一个元素），但分不清一棵单孩子子树是左孩子还是右孩子——前序后序的第二个元素都只能给出「子树的根」，给不出左右归属。除非题目额外限定是满二叉树。「复杂度？」哈希表定位根后，每个节点恰好被处理一次，时间 O(n)，递归栈深度等于树高，最坏 O(n)。「为什么要建下标哈希表？」把每次线性查找的 O(n) 压成 O(1)，这是本题从「能做对」到「做得好」的分水岭。
这套「从两个视角的序列重建结构」的思路远不止二叉树：解析器从 token 流重建语法树、从扁平配置重建树状状态、分布式日志从分片序列还原全局序，都是同一个建模范式——找到那个能把两个视角对齐的分治点。回到笔试现场，建议的答题节奏：先讲两条序列各自的信息量与无重复值前提，再给出分治下标推导，最后主动把复杂度从 O(n²) 优化到 O(n)。你刷题时遇到过「序列不自洽」的脏输入吗？是怎么处理的？欢迎聊聊。