DFS 与 BFS：递归、队列与图遍历

DFS：一条路走到黑，再回溯

DFS 的全称是 Depth-First Search，中文叫 深度优先搜索。它的核心策略是：

课程里给了一个非常简单的树：

AB CD

如果以先序遍历为例，DFS 的访问顺序是：A → B → D → C。

为什么是这个顺序？因为 DFS 会优先往深处走：

1. 从 A 开始；
2. 先访问左子节点 B；
3. 再从 B 继续往下，访问 D；
4. D 没有子节点了，回溯到 B，B 也没有其他子节点了，再回溯到 A；
5. 最后访问 A 的右子节点 C。

递归实现

DFS 最自然的实现方式是递归，因为“继续深入”和“回溯”恰好对应函数的调用栈和返回。

const tree = {value: 'A',children: [{value: 'B',children: [{ value: 'D', children: [] }]},{value: 'C',children: []}]};function dfs(node) {if (!node) return;// 1. 访问当前节点（先序遍历）console.log(node.value);// 2. 对每个子节点递归执行 DFSfor (const child of node.children) {dfs(child);}}dfs(tree); // 输出：A B D C

这里的递归调用栈自动帮我们完成了“回溯”：当 dfs(D) 执行完后，程序会自动回到 dfs(B) 的循环里，继续检查 B 是否还有其他子节点。

BFS：一层一层向外扩散

BFS 的全称是 Breadth-First Search，中文叫 广度优先搜索。它的策略和 DFS 正好相反：

如果用同样的树做层序遍历，顺序是：A → B → C → D。

队列实现

BFS 通常用队列实现。队列的“先进先出”特性，保证了我们能按层次处理节点：

function bfs(root) {if (!root) return;const queue = [root];while (queue.length > 0) {const node = queue.shift(); // 取出队首console.log(node.value);// 访问当前节点// 把子节点加入队尾for (const child of node.children) {queue.push(child);}}}bfs(tree); // 输出：A B C D

执行过程如下：

1. 队列初始：[A]；
2. 取出 A，输出 A，把 B、C 入队：[B, C]；
3. 取出 B，输出 B，把 D 入队：[C, D]；
4. 取出 C，输出 C，没有子节点：[D]；
5. 取出 D，输出 D，遍历结束。

DFS 与 BFS 的对比

特别强调一个直觉：DFS 适合“找路径”的问题，BFS 适合“找最短”的问题。因为 BFS 第一次到达某个节点时，经过的步数一定是最少的。

DFS 的另一种写法：用显式栈

常规是用递归实现 DFS，但递归有栈溢出风险（树特别深时）。实际面试和工程中，DFS 也经常用显式栈来模拟递归过程：

function dfsWithStack(root) {if (!root) return;const stack = [root];while (stack.length > 0) {const node = stack.pop(); // 取出栈顶console.log(node.value);// 访问当前节点// 注意：为了先访问左子节点，要先把右子节点入栈for (let i = node.children.length - 1; i >= 0; i--) {stack.push(node.children[i]);}}}dfsWithStack(tree); // 输出：A B D C

用栈的好处是可控，不会出现递归太深导致的调用栈溢出；缺点是代码稍微啰嗦一点。两种写法都要掌握。

经典题目练手

DFS 和 BFS 是 LeetCode 上出镜率最高的基础算法之一。下面选了几道经典题，覆盖树和图两种场景。

LC 104：二叉树的最大深度

思路：深度就是层数，每个节点的深度 = max(左子树深度, 右子树深度) + 1。这是 DFS 的递归思想。

function maxDepth(root) {if (!root) return 0;return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;}

LC 112：路径总和

思路：从根节点出发，不断减去当前节点的值，走到叶子节点时看剩余值是否为 0。

function hasPathSum(root, targetSum) {if (!root) return false;// 叶子节点if (!root.left && !root.right) {return targetSum === root.val;}return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);}

LC 102：二叉树的层序遍历

思路：典型的 BFS，按层处理节点，每层单独收集结果。

function levelOrder(root) {if (!root) return [];const result = [];const queue = [root];while (queue.length > 0) {const levelSize = queue.length;const currentLevel = [];for (let i = 0; i < levelSize; i++) {const node = queue.shift();currentLevel.push(node.val);if (node.left) queue.push(node.left);if (node.right) queue.push(node.right);}result.push(currentLevel);}return result;}

LC 111：二叉树的最小深度

思路：找最短路径，BFS 第一次遇到叶子节点时返回当前层数即可。

function minDepth(root) {if (!root) return 0;const queue = [[root, 1]];while (queue.length > 0) {const [node, depth] = queue.shift();if (!node.left && !node.right) {return depth;}if (node.left) queue.push([node.left, depth + 1]);if (node.right) queue.push([node.right, depth + 1]);}}

LC 200：岛屿数量

思路：网格里的 DFS/BFS 经典题。遍历每个格子，遇到陆地就启动一次搜索，把相连的陆地全部标记为已访问，岛屿数加 1。

function numIslands(grid) {if (!grid || grid.length === 0) return 0;const rows = grid.length;const cols = grid[0].length;let count = 0;function dfs(r, c) {if (r < 0 || r >= rows || c < 0 || c >= cols) return;if (grid[r][c] !== '1') return;grid[r][c] = '2'; // 标记为已访问dfs(r - 1, c);dfs(r + 1, c);dfs(r, c - 1);dfs(r, c + 1);}for (let r = 0; r < rows; r++) {for (let c = 0; c < cols; c++) {if (grid[r][c] === '1') {count++;dfs(r, c);}}}return count;}

这道题让我意识到，DFS 在网格问题里就是“朝四个方向继续走，越界或遇到水就回头”，和树里的递归思想完全一样，只是邻居变成了上下左右四个方向。

DFS / BFS 通用模板

把上面的题目抽象一下，可以整理出两个模板：

DFS 模板（递归版）：

function dfs(node, visited) {if (!node || visited.has(node)) return;visited.add(node);// 处理当前节点for (const neighbor of node.neighbors) {dfs(neighbor, visited);}}

BFS 模板：

function bfs(start) {const queue = [start];const visited = new Set([start]);while (queue.length > 0) {const node = queue.shift();// 处理当前节点for (const neighbor of node.neighbors) {if (!visited.has(neighbor)) {visited.add(neighbor);queue.push(neighbor);}}}}

在图结构里，一定要记得用 visited 集合记录已经访问过的节点，否则会出现死循环。

列表转树：list2tree

list2tree，这是实际开发中非常常见的需求。后端返回的往往是扁平数组，前端需要把它转成树形结构来渲染菜单、组织架构、评论回复等。

一个典型的扁平列表长这样：

const list = [{ id: 1, name: 'A', parentId: null },{ id: 2, name: 'B', parentId: 1 },{ id: 3, name: 'C', parentId: 1 },{ id: 4, name: 'D', parentId: 2 },];

转成树：

function list2tree(list) {const map = new Map();const roots = [];// 第一步：用 map 记录每个节点for (const item of list) {map.set(item.id, { ...item, children: [] });}// 第二步：把每个节点挂到父节点下面for (const item of list) {const node = map.get(item.id);if (item.parentId === null) {roots.push(node);} else {const parent = map.get(item.parentId);if (parent) {parent.children.push(node);}}}return roots;}console.log(JSON.stringify(list2tree(list), null, 2));

核心思路是：

1. 用 Map 把 id 和节点做映射，方便 O(1) 查找；
2. 遍历列表，把每个节点挂到对应的父节点下；
3. parentId === null 的节点就是根节点。

这个做法的时间复杂度是 O(n)，比嵌套循环查找父节点高效得多。

我现在怎么理解 DFS 和 BFS

DFS 和 BFS 不是两种孤立的算法，而是两种解决问题的“视角”。

• DFS 像是一个人在迷宫里不断探索，遇到死胡同就原路返回，适合把所有可能性都试一遍；
• BFS 像是一滴水落在湖面，波纹一圈一圈扩散出去，适合找最短、最近、最浅的东西。

list2tree 也让我意识到，算法知识和实际业务是连在一起的。后端给数组、前端要树，中间这一层转换看似简单，但背后用到的哈希映射和递归思想，正是 DFS 和 BFS 这类基础算法的延伸。

后续刷 LeetCode 时，很多题目本质上都是这两种遍历思路的变形。先把这个基础打牢，后面的回溯、动态规划、图论都会轻松很多。