树遍历专题（DFS/BFS 入门）
算法树DFSBFS二叉树
树遍历专题（DFS/BFS 入门）
📖 学习路径： 01 树遍历 → 02 DFS/BFS 进阶 → 03 动态规划
一、核心概念
1. DFS vs BFS
| 特性 | DFS（深度优先） | BFS（广度优先） |
|---|---|---|
| 数据结构 | 栈（递归调用栈 / 显式栈） | 队列 |
| 遍历方式 | 一条路走到底，再回溯 | 一层一层向外扩展 |
| 空间 | O(h)，h 为树高 | O(w)，w 为最大宽度 |
| 时间 | O(n) | O(n) |
2. 快速决策
需要最短路径/层级信息？
├── 是 → BFS（层序遍历、最小深度、右视图）
└── 否 → 需要记录完整路径？
├── 是 → DFS + 回溯（路径总和 II）
└── 否 → DFS 递归（最大深度、路径总和、平衡树）3. 本专题统一代码风格
约定： 以下所有代码使用相同的写法模式，方便对照理解。
- 类型注解完整（
TreeNode[]、number[][]等）- 条件判断用
while (queue.length > 0)而非while (queue.length)- 结果变量统一命名为
result- DFS 内部函数统一命名为
dfs- 队列/栈变量统一命名：
queue/stack
二、代码框架（本专题通用模板）
框架一：DFS 递归（树遍历核心模板）
const dfsRecursive = (root: TreeNode | null): number[] => {
const result: number[] = [];
const dfs = (node: TreeNode | null) => {
if (!node) return; // ① 终止条件：空节点
// ② 处理当前节点（位置决定遍历顺序）
dfs(node.left); // ③ 递归左子树
dfs(node.right); // ④ 递归右子树
};
dfs(root);
return result;
};💡 改变
result.push(node.val)的位置 = 前序/中序/后序
框架二：BFS 层序遍历（按层处理）
const bfsLevelOrder = (root: TreeNode | null): number[][] => {
if (!root) return [];
const result: number[][] = [];
const queue: TreeNode[] = [root]; // ① 初始化队列
while (queue.length > 0) { // ② 队列不空就继续
const levelSize = queue.length; // ③ 记录当前层大小
const level: number[] = [];
for (let i = 0; i < levelSize; i++) { // ④ 处理当前层
const node = queue.shift()!;
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level); // ⑤ 收集当前层结果
}
return result;
};三、典型例题（由简到难）
🟢 基础遍历
1. 二叉树的前/中/后序遍历（LeetCode 144/94/145）
问题： 给定二叉树的根节点，按前序（根→左→右）、中序（左→根→右）、后序（左→右→根）返回遍历结果。
思路： 三种遍历的区别仅在于 result.push(node.val) 的位置。
前序：访问 → 左递归 → 右递归 【根左右】
中序：左递归 → 访问 → 右递归 【左根右】
后序：左递归 → 右递归 → 访问 【左右根】递归版（统一模板）：
// ========== 前序：根 → 左 → 右 ==========
const preorderRecursive = (root: TreeNode | null): number[] => {
const result: number[] = [];
const dfs = (node: TreeNode | null) => {
if (!node) return;
result.push(node.val); // ← 访问在递归前
dfs(node.left);
dfs(node.right);
};
dfs(root);
return result;
};
// ========== 中序：左 → 根 → 右 ==========
const inorderRecursive = (root: TreeNode | null): number[] => {
const result: number[] = [];
const dfs = (node: TreeNode | null) => {
if (!node) return;
dfs(node.left);
result.push(node.val); // ← 访问在左右递归之间
dfs(node.right);
};
dfs(root);
return result;
};
// ========== 后序：左 → 右 → 根 ==========
const postorderRecursive = (root: TreeNode | null): number[] => {
const result: number[] = [];
const dfs = (node: TreeNode | null) => {
if (!node) return;
dfs(node.left);
dfs(node.right);
result.push(node.val); // ← 访问在递归后
};
dfs(root);
return result;
};迭代版（显式栈）：
// ========== 前序迭代：栈 → 弹出访问 → 先压右再压左 ==========
const preorderIterative = (root: TreeNode | null): number[] => {
if (!root) return [];
const result: number[] = [];
const stack: TreeNode[] = [root];
while (stack.length > 0) {
const node = stack.pop()!;
result.push(node.val);
if (node.right) stack.push(node.right); // 先压右
if (node.left) stack.push(node.left); // 后压左（先出栈）
}
return result;
};
// ========== 中序迭代：一路向左 → 弹出访问 → 转向右 ==========
const inorderIterative = (root: TreeNode | null): number[] => {
const result: number[] = [];
const stack: TreeNode[] = [];
let cur = root;
while (cur || stack.length > 0) {
while (cur) { // 一路向左压栈
stack.push(cur);
cur = cur.left;
}
cur = stack.pop()!; // 弹出访问
result.push(cur.val);
cur = cur.right; // 转向右子树
}
return result;
};
// ========== 后序迭代：前序"根右左"的反转 = "左右根" ==========
const postorderIterative = (root: TreeNode | null): number[] => {
if (!root) return [];
const result: number[] = [];
const stack: TreeNode[] = [root];
while (stack.length > 0) {
const node = stack.pop()!;
result.push(node.val);
if (node.left) stack.push(node.left); // 先压左
if (node.right) stack.push(node.right); // 后压右
}
return result.reverse(); // 反转即得后序
};记忆技巧：
| 遍历 | 递归写法 | 迭代技巧 |
|---|---|---|
| 前序 | push → left → right | 栈，先压右再压左 |
| 中序 | left → push → right | 一路向左，弹出访问 |
| 后序 | left → right → push | 前序“根右左”的反转 |
2. 二叉树的层序遍历（LeetCode 102）
问题： 按从上到下、从左到右的顺序，逐层返回节点值。
思路： BFS 模板直接套用，levelSize 控制每层处理数量。
const levelOrder = (root: TreeNode | null): number[][] => {
if (!root) return [];
const result: number[][] = [];
const queue: TreeNode[] = [root];
while (queue.length > 0) {
const levelSize = queue.length; // ① 当前层的节点数
const level: number[] = [];
for (let i = 0; i < levelSize; i++) { // ② 只处理当前层
const node = queue.shift()!;
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level); // ③ 收集当前层
}
return result;
};执行过程：
3
/ \
9 20
/ \
15 7
第1轮：levelSize=1, 处理[3], 入队[9,20] → result=[[3]]
第2轮：levelSize=2, 处理[9,20], 入队[15,7] → result=[[3],[9,20]]
第3轮：levelSize=2, 处理[15,7], 入队[] → result=[[3],[9,20],[15,7]]🟡 深度/高度相关
3. 二叉树的最大深度（LeetCode 104）
问题： 求二叉树的最大深度（根节点到最远叶子节点的路径上的节点数）。
思路：
- DFS：当前深度 = max(左子树深度, 右子树深度) + 1
- BFS：每处理一层，深度 +1
// ====== DFS 版：自底向上 ======
const maxDepthDFS = (root: TreeNode | null): number => {
if (!root) return 0;
return Math.max(maxDepthDFS(root.left), maxDepthDFS(root.right)) + 1;
};
// ====== BFS 版：自顶向下（按层计数） ======
const maxDepthBFS = (root: TreeNode | null): number => {
if (!root) return 0;
const queue: TreeNode[] = [root];
let depth = 0;
while (queue.length > 0) {
const levelSize = queue.length;
for (let i = 0; i < levelSize; i++) {
const node = queue.shift()!;
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
depth++; // 每处理完一层，深度 +1
}
return depth;
};执行过程（DFS 版）：
3
/ \
9 20
/ \
15 7
maxDepth(3)
→ max( maxDepth(9), maxDepth(20) ) + 1
→ max( 1, max(maxDepth(15), maxDepth(7)) + 1 ) + 1
→ max( 1, max(1, 1) + 1 ) + 1
→ max( 1, 2 ) + 1
→ 34. 二叉树的最小深度（LeetCode 111）
问题： 求二叉树的最小深度（根节点到最近叶子节点的路径上的节点数）。
思路： BFS 天然优势——第一个遇到的叶子节点所在层就是最小深度。
const minDepth = (root: TreeNode | null): number => {
if (!root) return 0;
const queue: TreeNode[] = [root];
let depth = 0;
while (queue.length > 0) {
const levelSize = queue.length;
depth++;
for (let i = 0; i < levelSize; i++) {
const node = queue.shift()!;
// 叶子节点：左右都为空，直接返回当前深度
if (!node.left && !node.right) return depth;
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
return depth;
};💡 BFS 天然适合求最小深度：第一个叶子节点所在的深度就是答案。DFS 也可以做，但需要额外处理“只有单侧子树”的情况。
5. 平衡二叉树（LeetCode 110）
问题： 判断二叉树是否是平衡二叉树（任意节点的左右子树高度差不超过 1）。
思路： 自底向上递归，用 -1 标记不平衡状态，避免重复计算高度。
const isBalanced = (root: TreeNode | null): boolean => {
// 返回高度，如果不平衡则返回 -1
const getHeight = (node: TreeNode | null): number => {
if (!node) return 0;
const leftH = getHeight(node.left);
const rightH = getHeight(node.right);
// 子树不平衡，或当前节点高度差 > 1 → 返回 -1
if (leftH === -1 || rightH === -1 || Math.abs(leftH - rightH) > 1) {
return -1;
}
return Math.max(leftH, rightH) + 1;
};
return getHeight(root) !== -1;
};执行过程：
1
/ \
2 2 ← 节点2：左右高度差=0，返回1
/ \ / \
3 3 3 3 ← 节点3：叶子，返回1
\
4 ← 节点4：叶子，返回1
getHeight(3-最右): left=0, right=1, |0-1|=1≤1 → 返回2
getHeight(2-右): left=2, right=2, |2-2|=0≤1 → 返回3
getHeight(1): left=3, right=3, |3-3|=0≤1 → 返回4
isBalanced = true ✅🟠 路径/视图相关
6. 路径总和（LeetCode 112）
问题： 判断二叉树中是否存在根→叶路径，其节点值之和等于
targetSum。
思路： DFS 递归，每深入一层减去当前节点值，到叶子时检查剩余值是否为 0。
const hasPathSum = (root: TreeNode | null, targetSum: number): boolean => {
if (!root) return false;
// 到达叶子节点：检查当前值是否等于剩余目标值
if (!root.left && !root.right) {
return root.val === targetSum;
}
// 递归检查左右子树，目标值减去当前节点值
return hasPathSum(root.left, targetSum - root.val)
|| hasPathSum(root.right, targetSum - root.val);
};执行过程（targetSum = 22）：
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
hasPathSum(5, 22)
→ hasPathSum(4, 17) ← 22-5=17
→ hasPathSum(11, 13) ← 17-4=13
→ hasPathSum(7, 2) ← 13-11=2 → 7≠2 → false
→ hasPathSum(2, 2) ← 2==2 → true ✅7. 路径总和 II（LeetCode 113）
问题： 找出所有根→叶路径，使得路径上节点值之和等于
targetSum，返回具体路径。
思路： DFS + 回溯。因为 path 数组是引用类型，多分支共享，必须 push → 递归 → pop。
const pathSum = (root: TreeNode | null, targetSum: number): number[][] => {
const result: number[][] = [];
const path: number[] = [];
const dfs = (node: TreeNode | null, remaining: number) => {
if (!node) return;
path.push(node.val); // ① 选择当前节点
// ② 叶子节点 + 值匹配 → 收集路径（深拷贝）
if (!node.left && !node.right && remaining === node.val) {
result.push([...path]);
}
dfs(node.left, remaining - node.val); // ③ 递归子节点
dfs(node.right, remaining - node.val);
path.pop(); // ④ 回溯：撤销当前选择，回到上一层的状态
};
dfs(root, targetSum);
return result;
};为什么需要回溯？ 因为 path 是引用类型，递归调用中所有分支共享同一个数组。
5
/ \
4 8
/ / \
11 13 4
targetSum=22 的调用过程：
path=[5]
→ path=[5,4]
→ path=[5,4,11]
→ path=[5,4,11,7] → 7≠11 → pop(7)
→ path=[5,4,11,2] → 2==11 → 收集 [5,4,11,2] ✅ → pop(2)
→ pop(11) ← 回到 [5,4]
→ pop(4) ← 回到 [5]
→ path=[5,8]
→ path=[5,8,13] → 13≠9 → pop(13)
→ path=[5,8,4] → 需要继续...8. 二叉树的右视图（LeetCode 199）
问题： 从二叉树的右侧看，返回能看到的节点值（每层最右边的节点）。
思路： BFS 层序遍历，每层的最后一个节点就是右视图看到的节点。
const rightSideView = (root: TreeNode | null): number[] => {
if (!root) return [];
const result: number[] = [];
const queue: TreeNode[] = [root];
while (queue.length > 0) {
const levelSize = queue.length;
for (let i = 0; i < levelSize; i++) {
const node = queue.shift()!;
// 每层最后一个节点 = 右视图看到的节点
if (i === levelSize - 1) {
result.push(node.val);
}
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
return result;
};执行过程：
1 ← 看到 1
/ \
2 3 ← 看到 3
\ \
5 4 ← 看到 4
/
6 ← 看到 6
result = [1, 3, 4, 6]🔴 多叉树扩展
9. N 叉树的前/后序遍历（LeetCode 589/590）
问题： 给定 N 叉树的根节点，返回前序/后序遍历结果。
与二叉树的区别： 二叉树用 node.left / node.right，N 叉树用 for (child of node.children)。
节点定义：
class Node {
val: number;
children: Node[];
constructor(val: number) {
this.val = val;
this.children = [];
}
}前序和后序：
// ========== 前序：先访问根，再遍历子节点 ==========
const preorderNary = (root: Node | null): number[] => {
const result: number[] = [];
const dfs = (node: Node | null) => {
if (!node) return;
result.push(node.val); // 访问当前
for (const child of node.children) { // 遍历子节点
dfs(child);
}
};
dfs(root);
return result;
};
// ========== 后序：先遍历子节点，再访问根 ==========
const postorderNary = (root: Node | null): number[] => {
const result: number[] = [];
const dfs = (node: Node | null) => {
if (!node) return;
for (const child of node.children) { // 先遍历子节点
dfs(child);
}
result.push(node.val); // 再访问当前
};
dfs(root);
return result;
};10. N 叉树的最大深度（LeetCode 559）
问题： 求 N 叉树的最大深度。
思路： 当前深度 = max(所有子节点的深度) + 1。
const maxDepthNary = (root: Node | null): number => {
if (!root) return 0;
let maxChildDepth = 0;
for (const child of root.children) {
maxChildDepth = Math.max(maxChildDepth, maxDepthNary(child));
}
return maxChildDepth + 1;
};二叉树 vs N叉树 最大深度对比：
// 二叉树：直接取左右子树
return Math.max(dfs(root.left), dfs(root.right)) + 1;
// N叉树：遍历所有子节点取最大
let max = 0;
for (const child of root.children) {
max = Math.max(max, dfs(child));
}
return max + 1;🟣 对称/结构相关
11. 对称二叉树（LeetCode 101）
问题： 判断二叉树是否关于中心轴对称。
思路： 双指针递归——同时比较左子树的左节点与右子树的右节点、左子树的右节点与右子树的左节点。
const isSymmetric = (root: TreeNode | null): boolean => {
if (!root) return true;
// 比较两棵子树是否镜像对称
const isMirror = (p: TreeNode | null, q: TreeNode | null): boolean => {
if (!p && !q) return true; // 都为空 → 对称
if (!p || !q) return false; // 一个为空 → 不对称
if (p.val !== q.val) return false; // 值不同 → 不对称
// 递归比较：p的左 vs q的右 AND p的右 vs q的左
return isMirror(p.left, q.right) && isMirror(p.right, q.left);
};
return isMirror(root.left, root.right);
};执行过程：
1
/ \
2 2 ← isMirror(2, 2): 值相同
/ \ / \
3 4 4 3 ← isMirror(3,3): 值相同 ✅
isMirror(4,4): 值相同 ✅
✅ 对称
1
/ \
2 2 ← isMirror(2, 2): 值相同
\ \
3 3 ← isMirror(3, null): 一个空 → ❌ 不对称四、本专题总结
题目速查表
| # | 题目 | 方法 | 关键技巧 |
|---|---|---|---|
| 1 | 前/中/后序遍历 | DFS递归 + 迭代栈 | push 位置决定遍历顺序 |
| 2 | 层序遍历 | BFS队列 | levelSize 按层控制 |
| 3 | 最大深度 | DFS/BFS | DFS: max(左,右)+1；BFS: 每层 depth++ |
| 4 | 最小深度 | BFS | 首次遇到叶子即返回 |
| 5 | 平衡二叉树 | DFS递归 | -1 标记不平衡，自底向上 |
| 6 | 路径总和 | DFS递归 | 减法传递剩余值 |
| 7 | 路径总和 II | DFS + 回溯 | push → 递归 → pop |
| 8 | 右视图 | BFS | i === levelSize - 1 |
| 9 | N叉树遍历 | DFS递归 | for (child of children) |
| 10 | N叉树最大深度 | DFS递归 | 遍历子节点取最大 |
| 11 | 对称二叉树 | DFS双指针 | isMirror(左.左, 右.右) && isMirror(左.右, 右.左) |
统一代码模板回顾
| 场景 | 模板 |
|---|---|
| 树遍历（需全部结果） | DFS 递归：dfs(node.left); dfs(node.right) |
| 按层处理 | BFS 队列 + levelSize |
| 求最短/最小 | BFS：首次满足条件即返回 |
| 记录路径 | DFS + 回溯：push → 递归 → pop |
| 自底向上求值 | DFS：return f(左) 运算 f(右) + 1 |
记忆口诀
- 求最短，用 BFS
- 找路径，用 DFS
- 要分层，BFS 稳
- N叉树，循环子
- 回溯记路径，push 再 pop
- 自底向上，递归返回值
关联题库
以下题目与本文知识点相关，可以跳转到题库练习：