遍历视角：回溯与 DFS

DFS 与网格题

DFS 的主场是网格和图

回溯和 DFS 是同一棵递归树上的两种写法（差别下一篇讲透）。 但它们各有自己顺手的题型：

  • 回溯擅长「枚举所有可能」—— 排列、组合、子集、N 皇后
  • DFS 擅长「把连通的一片走完」—— 岛屿、区域、图的连通分量

这一篇讲后者。网格题是 DFS 最典型、模板最固定的场景。

岛屿数量

题意复述：给一个由 '1'（陆地）和 '0'（水）组成的二维网格， 上下左右相连的陆地算一座岛，问一共有几座。

function numIslands(grid) {
  if (!grid.length) return 0;
  const m = grid.length, n = grid[0].length;
  let count = 0;

  function dfs(i, j) {
    // 出界
    if (i < 0 || i >= m || j < 0 || j >= n) return;
    // 不是陆地（是水，或者已经被淹过）
    if (grid[i][j] !== '1') return;

    grid[i][j] = '0';        // ⭐ 淹没：兼做 visited

    dfs(i + 1, j);
    dfs(i - 1, j);
    dfs(i, j + 1);
    dfs(i, j - 1);
  }

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === '1') {
        count++;             // 发现一座新岛
        dfs(i, j);           // 把它整座淹掉
      }
    }
  }

  return count;
}

思路一句话：见到一块没淹过的陆地就计数加一，然后把跟它连着的全淹了。 淹完之后这座岛不可能被数第二次。

🚨 少了 visited 就是死循环

这是网格 DFS 与二叉树 DFS 最本质的区别，也是这一篇唯一必须记住的。

二叉树的递归天然会终止，因为树没有环 —— 从父节点走到子节点，永远回不来。

网格不是树，它处处是环：从 (0,0) 走到 (0,1)， 而 (0,1) 的四个方向里又包含 (0,0)。不做标记的话，两个格子之间会无限来回。

⚠️ 症状是 RangeError: Maximum call stack size exceeded，不是程序卡死。 实测一个 2×2 的全陆地网格、不做标记：0 ms 就抛出来了， 连「卡一下」的感觉都没有。所以看到栈溢出，除了想「递归太深」， 也要想「是不是忘了标记已访问」—— 这两种原因的修法完全不同，而报错信息对此只字不提。 ⭐ 一个快速分辨法：忘标记的溢出跟输入规模无关，2×2 都能崩； 真的递归太深要喂到很大的输入才崩。

⭐ 上面的代码没有单独的 visited 数组，因为**「淹没」本身就是标记**： '1' 改成 '0' 之后，if (grid[i][j] !== '1') return; 这一行就把它拦住了。 一举两得，还省掉一个 O(mn) 的数组。

⚠️ 代价是修改了输入。面试时顺口说一句「我这里直接改了原数组， 不允许修改的话我用一个 visited」——这句话本身就是加分项。

「先判越界，再判内容」的顺序不能反

if (i < 0 || i >= m || j < 0 || j >= n) return;   // 必须在前
if (grid[i][j] !== '1') return;

🚨 反过来写会先访问 grid[i][j]，而 i 可能是 -1 或 m。 JavaScript 里 grid[-1] 是 undefined，接着 undefined[j] 直接抛 TypeError: Cannot read properties of undefined。

⚠️ 有意思的是只有行方向越界才崩。列方向越界时 grid[i][-1] 是 undefined， 不抛错，只是那个格子被当成「不是陆地」跳过 —— 碰巧结果还是对的。

grid[-1][0]   → TypeError            行越界：grid[-1] 是 undefined，再 [0] 就炸
grid[0][-1]   → undefined（不抛）     列越界：只是取不到值

🚨 但别把这当成「这个 bug 很隐蔽」。 实测 5000 个随机网格， 顺序写反的版本崩了 91.0% —— 跑通的那 452 个答案倒是全对。

⭐ 它真正的盲区判据不是「列越界」，而是陆地碰不碰第 0 行和最后一行：

随机网格 5000 个                    崩 91.0%
边界一圈全是水（陆地碰不到上下边界）  崩  0.0%   3000 个一次都没崩，答案也全对

[['0','0','0'],           孤岛在正中央 → 四个方向都不出界 → 不崩
 ['0','1','0'],
 ['0','0','0']]

[['1','0'],               陆地在第 0 行 → dfs(i-1,j) 立刻行越界 → 必崩
 ['0','0']]

👉 因为只要有一块陆地落在第 0 行或最后一行，dfs(i∓1, j) 马上就行越界。 「只会列越界」要求陆地完全避开上下两行，随机网格里只占约 9%。 📌 所以自测时专门放一块陆地在第 0 行 —— 一次就暴露。

方向数组

四行 dfs(i±1, j) / dfs(i, j±1) 在四方向时够用，八方向就很难看了。通用写法：

const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];

function dfs(i, j) {
  if (i < 0 || i >= m || j < 0 || j >= n) return;
  if (grid[i][j] !== '1') return;
  grid[i][j] = '0';

  for (const [di, dj] of DIRS) {
    dfs(i + di, j + dj);
  }
}

📌 改成八方向（含对角线）只需要把 DIRS 换成 8 项，其余一行不动。

变体：面积与封闭岛屿

最大岛屿面积 —— 让 dfs 返回它淹掉的格子数：

function area(grid, i, j) {
  if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return 0;
  if (grid[i][j] !== 1) return 0;
  grid[i][j] = 0;
  return 1
    + area(grid, i + 1, j) + area(grid, i - 1, j)
    + area(grid, i, j + 1) + area(grid, i, j - 1);
}

⭐ 注意这里切回了子问题视角—— 用返回值把面积拼起来，而不是用外部变量累加。 两种视角在网格题里同样通用，挑顺手的用。

封闭岛屿（不接触边界的岛）—— 套路是先把边界上的岛全淹掉， 剩下的自然都是封闭的，再按常规数一遍。 「先排除，再统计」比在 dfs 里判断「这条路有没有碰到边界」干净得多， 后者还得把一个布尔标志在递归里传来传去。

复杂度

每个格子最多被淹一次（第一次访问就被淹了），所以是 O(m × n)。 空间是递归深度，最坏情况下整个网格连成一片，深度也是 O(m × n)。

⚠️ 但「被淹一次」和「dfs 被调用一次」是两回事，实测差着五倍：

规模        陆地格子   dfs 调用次数   调用 / 陆地
10×10             54           226        4.19
30×30            454          1885        4.15
100×100         4931         20457        4.15

淹没次数在三个规模上都恰好等于陆地格子数，一次不多。 但每个陆地格子会发出 4 次递归调用，其中三次立刻撞上「已经淹了」返回 —— 所以调用次数稳定在陆地数的约 4.15 倍。数量级不变，常数别忽略。

那个「一万层」是多少

正文常说的「JS 栈只有约一万层」是个粗略上界。能撑多深取决于每帧多大， 拿一条 1×N 的全陆地走廊逼这个 dfs 到溢出，实测：

                        真冷启动（全新进程，首次调用）    同进程预热后
这个 dfs（2 参数 + 闭包）          6869                      7871
两参数的空函数                     7851                        —
无参数的空函数                     9159                        —

⭐ 三个数都不到一万，而且函数越“胖”能撑越浅 —— 这个 dfs 只有约 6900 层。 ⚠️ 冷启动与预热差 1.15×（6869 → 7871）。量这类数字时必须说清是哪种条件： 用二分法找临界值的话，二分本身就把 JIT 预热掉了，量出来的不是冷启动。 详见怎么理解递归。

👉 结论不变：1000 × 1000 的网格要百万级深度，必然栈溢出（差了两个数量级）。 真遇到这种规模得改用 BFS（队列不占调用栈）或者显式栈。 算法题里通常给不到这个量级，但心里要有数。

下一步

回溯和 DFS 都写过了，但它们的区别一直没说透。 下一篇专门讲那个「一个位置之差」。

练习

勾选记录做过哪些，0 / 6 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。