深度优先遍历 (Depth-First Search, DFS)
1. DFS 核心概览
深度优先遍历（DFS）是一种用于遍历或搜索树或图的算法。它的核心思想是：“不到黄河心不死”。从起始节点开始，沿着一条路径不断向下钻取，直到遇到叶子节点（或死胡同），然后退回（回溯）到上一个分叉口，继续探索下一条路径。
通俗理解： 走迷宫时，你一直贴着右边的墙壁走，遇到死胡同就退回上一个路口，换一条路继续贴着墙壁走，直到走遍整个迷宫。
1.1 DFS 的核心利器：栈 (Stack)
与 BFS 依赖“队列”不同，DFS 极其依赖栈（后进先出 LIFO）。 在实际编码中，DFS 有两种实现方式：
- 隐式栈（递归）： 利用 JavaScript 引擎自身的“函数调用栈（Call Stack）”。代码极其简洁优雅，是日常开发和面试的首选。
- 显式栈（迭代）： 手动创建一个数组
[]模拟栈。主要用于树极深、递归容易爆栈的极端场景。
1.2 DFS 的王牌应用场景
| 应用场景 | 详细说明 |
|---|---|
| 连通性问题 | 寻找图中有多少个独立连通的区域（如著名的“岛屿数量”问题）。 |
| 寻找所有路径 | 走迷宫找寻所有可行的路径（即之前探讨过的回溯算法）。 |
| 树的各类遍历 | 前序遍历（根左右）、中序遍历（左根右）、后序遍历（左右根）。 |
| 拓扑排序 / 环检测 | 判断一个图中是否存在死循环（如检测 NPM 包的循环依赖）。 |
2. 经典 DFS 场景与 JavaScript 实现
2.1 二叉树的基础遍历 (Tree DFS)
在二叉树中，DFS 最经典的体现就是前、中、后序遍历。由于树没有环，我们不需要担心走回头路。
JavaScript 代码实现 (递归版前序遍历)
js
/**
* 二叉树前序遍历 (DFS - 根、左、右)
* @param {TreeNode} root
* @return {number[]}
*/
function preorderTraversal(root) {
const result = [];
// 定义 DFS 递归函数
function dfs(node) {
if (!node) return; // 终止条件：遇到空节点，停止下钻
result.push(node.val); // 1. 先处理当前节点 (根)
dfs(node.left); // 2. 疯狂向左子树下钻 (左)
dfs(node.right); // 3. 左边走不通了，再向右子树下钻 (右)
}
dfs(root);
return result;
}2.2 网格/图的 DFS：岛屿数量 (Number of Islands)
这是 LeetCode 上最经典的图论 DFS 题目。 题目描述： 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
核心逻辑： 遍历整个网格，一旦遇到 '1'，说明发现了一个新岛屿（数量+1）。然后立刻启动 DFS，像病毒感染一样，把与它相连的所有 '1' 都变成 '0'（即标记为已访问），防止后续遍历时重复计算。
JavaScript 代码实现
js
/**
* 岛屿数量
* @param {character[][]} grid
* @return {number}
*/
function numIslands(grid) {
if (!grid || grid.length === 0) return 0;
let count = 0;
const rows = grid.length;
const cols = grid[0].length;
// 定义 DFS 感染函数
function dfs(r, c) {
// 终止条件：越界，或者是水 ('0')，停止探索
if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === '0') {
return;
}
// 【关键】将当前陆地变成水 (标记为已访问)，防止死循环！
grid[r][c] = '0';
// 向四个方向继续深度感染
dfs(r - 1, c); // 上
dfs(r + 1, c); // 下
dfs(r, c - 1); // 左
dfs(r, c + 1); // 右
}
// 遍历整个网格找陆地
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (grid[i][j] === '1') {
count++; // 发现新岛屿
dfs(i, j); // 启动 DFS，把这整座岛屿全部“击沉”
}
}
}
return count;
}3. 常见问题深度剖析 (FAQ)
| 常见疑惑 | 深度解析与应对策略 |
|---|---|
| 1. DFS 和 回溯算法（Backtracking）到底是什么关系？ | 回溯是 DFS 的一种特殊形式。 DFS 强调的是“结构上的遍历”（把每个角落都看一遍）；而回溯强调的是“状态的记录与撤销”（走到这一步记录一下，退回来时要把状态恢复原样，以便探索另一条路）。在上面的“岛屿数量”中，我们把 1 变成 0 后没有变回 1，这是纯粹的 DFS；如果探索完还需要变回 1，那就是回溯。 |
| 2. DFS 找出来的路径是最短路径吗？ | 绝对不是！ DFS 找到的第一条路径，仅仅是它“一头扎到底”碰巧撞上的那条路，极其有可能是绕了十万八千里的大远路。找最短路径必须用 BFS。 DFS 只能回答“能不能走到”或“一共有几条路”。 |
| 3. 二叉树的 前序、中序、后序 为什么都属于 DFS？ | 因为它们本质上都是靠递归一路下钻到底。它们的唯一区别仅仅是**“处理当前节点数据的时机”**不同： 🔹 第一次经过该节点就处理：前序。 🔹 左子树全处理完了，退回到该节点时再处理：中序。 🔹 左右子树都处理完了，最后离开该节点前处理：后序。 |