二叉树遍历算法
二叉树算法是整个算法大厦的基石。二叉树可以拓展为多叉树，而多叉树的遍历正是 BFS 与 DFS 的基础；树的遍历加上环判断，即可升级为图的遍历。学会二叉树遍历，就掌握了所有数据结构的遍历法则。
前置知识
DFS 遍历框架
本章聚焦树上的 DFS。网格/图上的 DFS（Flood Fill、连通分量等）见深度优先搜索专题。
二叉树 DFS 分为前中后序三种，划分依据只有一条：在什么时机处理当前节点的数据。
前序在进入左右子节点之前处理；中序在遍历完左子树、准备遍历右子树之前处理；后序在左右子树都遍历完成后处理。
function dfs(node: TreeNode | null) {
if (!node) return;
// 前序位置（进入节点时）
dfs(node.left);
// 中序位置（左子树处理完，右子树处理前）
dfs(node.right);
// 后序位置（离开节点时）
}若希望写成一个空间复杂度更低的非递归模板，可以直接套下面这个统一框架。和递归一样，只要在对应位置写逻辑即可：
function dfs(root: TreeNode) {
const stack: TreeNode[] = [];
let node: TreeNode = root;
// 只有后序遍历时需要额外记录上一次访问的节点
let prev: TreeNode | null = null;
while (node || stack.length) {
// 先压栈所有左子树
while (node) {
// 前序：如果是前序遍历，在这里处理 node
// doPre(node);
stack.push(node);
node = node.left;
}
// 1. 非后序的场景：直接转向右子树
/**
* const cur = stack.pop();
* 中序：左子树已经全部处理完了，在这里处理当前节点
* doIn(cur);
*
* node = cur.right;
*/
// 2. 后序的场景
const peek = stack[stack.length - 1];
// 右子树未处理过则先处理右子树
if (peek.right && prev !== peek.right) {
node = peek.right;
} else {
const cur = stack.pop();
// 后序：右子树已经在刚才处理过了，才能处理当前节点
// doPost(cur);
prev = cur;
}
}
}只写 doPre 就是前序，只写 doIn 就是中序，只写 doPost 就是后序；三者也可以组合使用。
BFS 遍历框架
本章聚焦树上的 BFS（层序遍历）。BFS 求最短路径、多源 BFS、抽象状态空间搜索等应用见广度优先搜索专题。
BFS（层序遍历）的核心是队列：每次弹出一层节点，再把下一层节点入队。
function bfs(root: TreeNode | null): number[][] {
if (!root) return [];
const res: number[][] = [];
const queue: TreeNode[] = [root];
while (queue.length) {
const level: number[] = [];
// 固定住当前层的节点数量，避免和下一层混在一起
const len = queue.length;
while(len--) {
const node = queue.shift()!;
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
res.push(level);
}
return res;
}如果题目是最短步数/最小深度这类最短路径问题，可以直接把 res 换成 depth 计数器：每处理完一层，depth++；首次命中目标就立刻返回。
前序、中序、后序的本质区别
理解三种遍历方式的信息流方向，是选择正确解法的关键：
| 遍历位置 | 可获取的信息 | 信息流方向 | 适用场景 |
|---|---|---|---|
| 前序 | 仅父节点传递下来的参数 | 自顶向下（Top-Down） | 传递状态、路径记录 |
| 中序 | 左子树已处理完毕 | 左 → 根 → 右 | BST 有序操作 |
| 后序 | 左右子树的完整结果（通过返回值） | 自底向上（Bottom-Up） | 需要子树信息的计算 |
核心规律：前序位置的代码只能从函数参数中获取父节点传递来的数据；而后序位置的代码不仅可以获取参数数据，还可以获取子树通过函数返回值传递回来的数据。
例如在 [257] 二叉树的所有路径 中，我们需要把从根到叶的路径通过参数一路往下传递，这就是典型的前序位置（Top-Down）处理。而在 [110] 平衡二叉树 中，我们需要先知道左右子树各自的高度，才能判断当前节点是否平衡，这就只能在后序位置（Bottom-Up）完成。
两种思维模式
掌握了前中后序的信息流方向后，还需要了解二叉树的两种底层解题思维，它们贯穿后续所有题型：
- 遍历思维：用
traverse函数遍历整棵树，配合外部变量累积结果，不需要返回值。 - 分解问题思维：用有返回值的递归函数，通过子问题（子树）的答案推导原问题的答案。
这两种思维不是题型分类，而是编码手段——同一道题往往两种思维都能解，区别在于哪种写起来更自然。后续每个题型中会标注其更适合的思维模式。
面对一道二叉树题目时，按以下顺序思考：
- 单独抽出一个节点，它需要做什么？
- 它需要在什么时机（前序 / 中序 / 后序位置）做？
- 用遍历思维还是分解问题思维更自然？
解题决策树
有了前置知识后，拿到一道二叉树题目，按以下决策树选择解法。前四类是基础遍历的直接应用，后三类是在此基础上的组合与进阶：
拿到一道二叉树题目
│
│ ── 基础遍历应用 ──
│
├─ 需要从根向下传递状态/路径？
│ └─ 是 → 前序遍历 .......................... → 见「一」
│
├─ 是 BST 且涉及有序性？
│ └─ 是 → 中序遍历 .......................... → 见「二」
│
├─ 需要先拿到子树的计算结果，再推导当前节点？
│ └─ 是 → 后序遍历 .......................... → 见「三」
│
├─ 涉及逐层处理/层级/最短路径？
│ └─ 是 → BFS 层序遍历 ...................... → 见「四」
│
│ ── 组合与进阶 ──
│
├─ 需要构造一棵树？
│ └─ 是 → 分解问题思维（按区间建根） .......... → 见「五」
│
├─ 需要对子树做签名比较/重复检测？
│ └─ 是 → 后序遍历 + 序列化签名 .............. → 见「六」
│
└─ 需要找最近公共祖先？
└─ 是 → 后序遍历 + 分解问题 ................ → 见「七」一、前序遍历：自顶向下传递状态
判断关键词：根到叶、路径记录、状态下传、回溯撤销。
适用场景：需要从根节点出发，把状态/路径一路往下传递。
思维模式：遍历思维为主——在前序位置做选择，往下递归，到达叶节点时判断或收集结果。
1.1 根到叶路径
例如在 [112] 路径总和 中，从根节点出发，在前序位置将目标值减去当前节点值并传递给子节点，到达叶节点时判断剩余值是否为 0。
function traverse(node: TreeNode | null, path: number[], remain: number) {
if (!node) return;
// 关键1：前序做选择
path.push(node.val);
remain -= node.val;
// 关键2：叶节点做判定/收集
if (!node.left && !node.right && remain === 0) res.push([...path]);
traverse(node.left, path, remain);
traverse(node.right, path, remain);
// 关键3：回溯撤销
path.pop();
}题型参考（框架微调）：
| 题目 | 在前序框架上的微调点 |
|---|---|
[112] 路径总和 | 参数中携带剩余目标值，到叶节点判断是否为 0。 |
[113] 路径总和 II | 在 112 基础上增加 path 数组，命中后拷贝路径入结果。 |
[257] 二叉树的所有路径 | 仍是路径下传，只是叶节点时把路径转成字符串。 |
[129] 求根节点到叶节点数字之和 | 路径状态从数组改成数字累积：num = num * 10 + node.val。 |
[437] 路径总和 III | 单纯前序不够，通常改成“每个节点作为起点 + DFS”或前缀和。 |
1.2 结构判断与修改
翻转、展平、判断对称等操作，两种思维都可以使用。
例如 [226] 翻转二叉树，每个节点要做的事就是交换左右子节点，放在前序位置（先交换再递归）或后序位置（先递归再组装）都能正确完成。
// 遍历思维：前序位置直接修改
function invertTree(node: TreeNode | null): TreeNode | null {
if (!node) return null;
[node.left, node.right] = [node.right, node.left];
invertTree(node.left);
invertTree(node.right);
return node;
}后序写法也等价：先递归拿到 left/right，再在返回前交换组装。
题型参考（框架微调）：
| 题目 | 在框架上的微调点 |
|---|---|
[226] 翻转二叉树 | 前序直接交换左右子树，或后序拿到左右结果后再组装。 |
[101] 对称二叉树 | 把“比较同位”改成“比较镜像位”（左左对右右变左对右）。 |
[114] 二叉树展开为链表 | 前序收集访问顺序后重连，或后序返回链表尾节点做拼接。 |
二、中序遍历：BST 有序操作
判断关键词：BST、有序性、第 K 小、前驱后继、区间统计。
适用场景：题目涉及 BST，且需要利用其有序性。
核心原理：BST 的中序遍历结果是有序的。
这一部分是「二叉树遍历」专题里对 BST 的重点补充：聚焦中序有序性在解题中的直接应用，而不展开为独立的数据结构增删改查专题。
2.1 BST 的性质与中序有序性
二叉搜索树（BST）只需抓住两点：
- 对于任意节点
node，左子树所有值都小于node.val，右子树所有值都大于node.val。 - 任意节点的左右子树本身也都是 BST。
这两个特性直接推导出一个结论：BST 的中序遍历结果一定有序。所以涉及顺序统计（第 K 小、第 K 大、区间计数）时，中序遍历通常是首选。
例如在 [230] 二叉搜索树中第K小的元素 中，问题可以直接转化为“返回中序遍历的第 k 个节点值”：
function kthSmallest(root: TreeNode | null, k: number): number {
let rank = 0;
let ans = 0;
function dfs(node: TreeNode | null): void {
if (!node || rank >= k) return; // 关键：可提前退出
dfs(node.left);
if (++rank === k) ans = node.val;
dfs(node.right);
}
dfs(root);
return ans;
}题型参考（框架微调）：
| 题目 | 在 BST 框架上的微调点 |
|---|---|
[230] 二叉搜索树中第K小的元素 | 中序遍历 + 计数器，命中第 k 个后提前退出。 |
[98] 验证二叉搜索树 | 中序时维护 prev 保证严格递增，或用上下界递归。 |
[700] 二叉搜索树中的搜索 | 不必完整遍历，按值大小只走一侧子树。 |
[235] 二叉搜索树的最近公共祖先 | 利用大小关系剪枝：同在左/右则下探，否则当前即答案。 |
三、后序遍历：自底向上汇总结果
判断关键词：子树结果先算、返回值汇总、平衡/直径/路径和。
适用场景：当前节点的答案需要由左右子树的结果推导。这是二叉树中最常见的模式。
思维模式：分解问题思维为主——递归函数有明确返回值，在后序位置利用左右子树的返回值计算当前节点的结果。
3.1 属性计算类
求二叉树的某个属性值（深度、节点数、直径等）。共同特征：当前节点的答案可以由左右子树的答案直接推导。
例如在 [104] 二叉树的最大深度 中，当前节点的深度 = max(左子树深度, 右子树深度) + 1；在 [222] 完全二叉树的节点个数 中，节点数 = 左子树节点数 + 右子树节点数 + 1。
解题公式：当前节点属性 = f(left, right, node)
function solve(node: TreeNode | null): number {
// 返回“当前子树的核心属性”（如高度）
// base case
if (!node) return 0;
const left = solve(node.left);
const right = solve(node.right);
// 可选：用 left/right 更新全局答案（例如直径、平衡性、路径最值）
// updateGlobal(left, right, node.val);
// 返回给父节点的值
return Math.max(left, right) + 1;
}示例映射：
- 最大深度：返回高度。
- 节点总数：返回
left + right + 1。 - 二叉树直径：返回高度，同时用
left + right更新全局最大直径。
3.2 任意路径最值
路径可以从任意节点出发到任意节点时，每个节点返回"经过该节点的单边最大路径和"，在后序位置计算"双边路径和"并更新全局最优。
例如在 [124] 二叉树中的最大路径和 中，每个节点需要知道左右子树各自能贡献的最大路径和，这只有在后序位置才能拿到。
function maxPathSum(root: TreeNode | null): number {
let best = -Infinity;
function gain(node: TreeNode | null): number {
if (!node) return 0;
const left = Math.max(0, gain(node.left));
const right = Math.max(0, gain(node.right));
best = Math.max(best, left + right + node.val); // 双边更新全局
return Math.max(left, right) + node.val; // 单边返回父节点
}
gain(root);
return best;
}题型参考（框架微调）：
| 题目 | 在后序框架上的微调点 |
|---|---|
[104] 二叉树的最大深度 | 返回值定义为“子树高度”，公式是 max(left, right) + 1。 |
[110] 平衡二叉树 | 返回高度时附带平衡性判断；常用 -1 作为失衡哨兵提前剪枝。 |
[222] 完全二叉树的节点个数 | 通用后序可解，进阶可利用完全树性质按高度优化。 |
[124] 二叉树中的最大路径和 | 返回单边贡献，双边路径只用于更新全局最优。 |
[543] 二叉树的直径 | 与 124 同型：返回单边高度，统计双边路径长度。 |
四、BFS 层序遍历
判断关键词：逐层处理、最短步数、最小深度、队列扩散。
适用场景：涉及逐层处理、层级关系、最短路径。
标准代码模板见「前置知识 -> BFS 遍历框架」。本节不再重复模板，只关注如何按题意改造。
常见改造点
| 题型 | 在骨架中的改动点 |
|---|---|
| 标准层序遍历（102） | 每层结束 res.push(level) |
| 锯齿形层序遍历（103） | 按层号决定 level 是否反转后再入 res |
| 右视图（199） | 每层取最后一个访问节点值 |
| 每层最大值（515） | 每层循环中维护 levelMax |
| 最小深度（111） | 增加 depth；遇到首个叶节点立即返回 |
| 填充右侧指针（117） | 层内记录 prev，将 prev.next = node 逐个连接 |
BFS 的优势在于“按距离扩散”，所以最短路径/最小步数类问题通常优先考虑 BFS。
题型参考（框架微调）：
| 题目 | 在 BFS 骨架上的微调点 |
|---|---|
[102] 二叉树的层序遍历 | 每层收集 level，层结束后 res.push(level)。 |
[103] 二叉树的锯齿形层序遍历 | 按层号决定当前层正序还是反序。 |
[107] 二叉树的层序遍历 II | 正常层序后反转结果，或改为头插结果。 |
[199] 二叉树的右视图 | 每层取最后一个弹出的节点值。 |
[515] 在每个树行中找最大值 | 层内维护 levelMax，层结束写入结果。 |
[111] 二叉树的最小深度 | 增加 depth 计数，首次遇到叶节点立即返回。 |
[117] 填充每个节点的下一个右侧节点指针 II | 层内维护 prev 指针，顺序连接 prev.next = cur。 |
五、构造类
判断关键词：由序列建树、确定根节点、划分左右区间。
适用场景：从遍历序列或其他条件构造一棵二叉树。
这一章是分解问题思维在“反向建树”场景的应用，不再重复递归遍历基础框架。
思维模式：分解问题思维——构造整棵树 = 确定根节点 + 递归构造左子树 + 递归构造右子树。
例如在 [654] 最大二叉树 中，根节点就是数组中的最大值，最大值左侧构成左子树，右侧构成右子树。所有构造类题目都遵循这一模式，差异仅在于"如何确定根节点"和"如何划分左右子树的范围"。
代码模板
function build(
order1: number[], start1: number, end1: number,
order2: number[], start2: number, end2: number
): TreeNode | null {
if (start1 > end1) return null;
// 1. 确定根节点值（从前序/后序的首/尾元素获取）
const rootVal = getRootVal(order1, start1, end1);
const root = new TreeNode(rootVal);
// 2. 在另一个序列中找到根节点位置，计算左子树大小
const index = findIndex(order2, rootVal);
const leftSize = index - start2;
// 3. 递归构造左右子树
root.left = build(order1, ..., order2, ...); // 左子树范围
root.right = build(order1, ..., order2, ...); // 右子树范围
return root;
}从遍历序列反构造二叉树
理解每种遍历结果的特点，是反构造的关键：
前序遍历：根节点一定是其结果的第一个。 中序遍历：根节点左边是左子树的中序结果，右边是右子树的中序结果。 后序遍历：根节点一定是其结果的最后一个。
通过前序或后序确定根节点值，在中序中找到根节点位置即可划分左右子树，进而得到各序列中左右子树的起止位置。
三种经典构造的核心差异：
| 输入组合 | 根节点位置 | 结果唯一性 |
|---|---|---|
| 前序 + 中序 | 前序首元素 | 唯一 |
| 后序 + 中序 | 后序末元素 | 唯一 |
| 前序 + 后序 | 前序首元素，前序第二个元素定位左子树 | 不唯一 |
前序+后序结果不唯一，因为当节点仅有一棵子树时，无法判断其是左子树还是右子树。
优化技巧：使用 HashMap 存储中序遍历的 value → index 映射，避免每次递归都线性查找。
题型参考（框架微调）：
| 题目 | 在构造框架上的微调点 |
|---|---|
[105] 从前序与中序遍历序列构造二叉树 | 根取前序首元素，在中序中定位根并按左子树大小切分区间。 |
[106] 从中序与后序遍历序列构造二叉树 | 根取后序尾元素，其余划分逻辑与 105 对称。 |
[889] 根据前序和后序遍历构造二叉树 | 用前序第二个元素定位左子树范围，但结果通常不唯一。 |
[654] 最大二叉树 | 对照题：不依赖遍历序列，根由“当前区间最大值”直接确定。 |
六、序列化与子树比较
判断关键词：子树判等、重复子树、序列化签名、哈希统计。
适用场景：判断两棵树是否相同、是否为子树、寻找重复子树。
本章只讲“序列化签名”技巧；后序遍历的基础模板与返回值思路见第三章。
思维模式：分解问题思维——在后序位置将每棵子树序列化为字符串，用 HashMap 记录出现次数。
要拿到一棵子树的完整表示，必须先拿到左右子树结果再拼上当前节点，所以天然是后序位置。
// 伪代码：后序序列化 + 哈希计数
serialize(node):
if node == null: return "#"
left = serialize(node.left)
right = serialize(node.right)
sig = left + "," + right + "," + node.val
if count(sig) == 1: collect(node)
count(sig) += 1
return sig题型参考（框架微调）：
| 题目 | 在序列化/比较框架上的微调点 |
|---|---|
[572] 另一棵树的子树 | 主树每个节点都可作为候选根，做一次子树相同判断或签名匹配。 |
[297] 二叉树的序列化与反序列化 | 关注编码与解码互逆；先定遍历顺序，再处理空节点占位。 |
七、最近公共祖先（LCA）
判断关键词：两个目标节点、公共祖先、左右子树各命中一个。
适用场景：寻找两个节点的最近公共祖先。
思维模式：分解问题思维——在后序位置，一个节点能知道左右子树中是否包含目标节点。
例如在 [236] 二叉树的最近公共祖先 中，我们需要知道 p 和 q 是否分别存在于左右子树中——这个信息只有在后序位置才能获得。如果左右子树各自找到了一个目标节点，当前节点就是 LCA。
经典 LCA 模板：
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
if (!root || root === p || root === q) return root;
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
// 后序位置：根据左右子树的结果判断
if (left && right) return root;
return left ?? right;
}LCA 变体：
| 变体 | 关键差异 | 处理方式 |
|---|---|---|
| 标准 LCA（236） | p、q 一定存在 | 标准模板 |
| BST 的 LCA（235） | 利用 BST 有序性 | 比较值大小，走左/右子树 |
| 节点可能不存在（1644） | 需确认两个节点都找到 | 额外 boolean 标记 |
| 有父指针（1650） | 转化为链表交叉问题 | 等同于相交链表（160） |
BST 的 LCA 可以充分利用有序性优化：
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
// 关键：利用 BST 有序性只走一边
if (!root) return null;
if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
return root;
}总结：解题速查表
| 题型 | 遍历方式 | 思维模式 | 核心操作位置 |
|---|---|---|---|
| 根到叶路径 | 前序 | 遍历 | 前序位置做选择，叶节点判断 |
| 结构判断与修改（翻转/对称） | 前序或后序 | 两种皆可 | 前序直接改 / 后序组装 |
| BST 有序操作 | 中序 | 遍历 | 中序位置处理有序性 |
| 属性计算（深度/节点数/直径） | 后序 | 分解问题 | 后序位置组合左右结果 |
| 任意路径最值 | 后序 | 分解问题 | 后序位置更新全局最优 |
| 逐层处理/最短路径 | BFS | 遍历 | 每层循环处理 |
| 构造二叉树（反向建树） | 递归分解 | 分解问题 | 按区间确定根并划分左右子树 |
| 子树签名比较/重复检测 | 后序 | 分解问题 | 后序位置生成序列化签名 |
| 最近公共祖先 | 后序 | 分解问题 | 后序位置判断左右结果 |