LeetCode 200.岛屿数量求解遇RangeError：调用栈溢出

问题背景 #

在解决岛屿数量问题时，代码中的递归DFS函数持续触发RangeError: Maximum call stack size exceeded错误，以下是报错的实现代码和测试用例：

报错代码（index.js） #

function numIslands(grid) {
    let count = 0;
    // 遍历矩阵中的每个单元格
    for (let row = 0; row < grid.length; row++) {
        // 遍历列，假设所有行的列数相同
        for (let col = 0; col < grid[0].length; col++) {
            // 如果当前单元格是陆地
            if (grid[row][col] === '1') {
                count++;
                // 调用DFS淹没整个岛屿
                dfs(grid, row, col);
            }
        }
    }

    function dfs(grid, row, col) {
        // 边界判断：越界或当前是水域则返回
        if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] === '0') {
            return;
        }
        // 将当前单元格设为0（淹没）—— 这里是错误点！
        grid[row][col] === '0';
        // 递归遍历上下左右四个方向
        dfs(grid, row - 1, col); // 上
        dfs(grid, row + 1, col); // 下
        dfs(grid, row, col - 1); // 左
        dfs(grid, row, col + 1); // 右
    }

    return count;
}

测试用例 #

test("正确返回0个岛屿", () => {
  expect(
    numIslands([
      ["0", "0", "0", "0", "0"],
      ["0", "0", "0", "0", "0"],
      ["0", "0", "0", "0", "0"]
    ])
  ).toEqual(0);
});

test("正确返回1个岛屿", () => {
  expect(
    numIslands([
      ["1", "1", "1", "1", "0"],
      ["1", "1", "0", "1", "0"],
      ["1", "1", "0", "0", "0"],
      ["0", "0", "0", "0", "0"],
      ["0", "0", "0", "0", "0"]
    ])
  ).toEqual(1);
});

test("正确返回3个岛屿", () => {
  expect(
    numIslands([
      ["1", "1", "0", "0", "0"],
      ["1", "1", "0", "0", "0"],
      ["0", "0", "1", "0", "0"],
      ["0", "0", "0", "1", "1"]
    ])
  ).toEqual(3);
});

错误原因分析 #

栈溢出的核心问题是没有正确标记已访问的陆地：
在DFS函数中，你写了grid[row][col] === '0';——这是一个全等比较操作，没有对单元格进行赋值。这导致每次递归时，当前陆地单元格始终是'1'，递归会反复访问同一个单元格，无限循环直到调用栈被撑爆。

修复方案 #

把比较操作改成赋值操作：

// 错误写法
// grid[row][col] === '0';
// 正确写法
grid[row][col] = '0';

修正后的完整代码 #

function numIslands(grid) {
    let count = 0;
    // 处理空网格的边界情况，避免grid[0].length报错
    if (!grid || grid.length === 0) return 0;
    for (let row = 0; row < grid.length; row++) {
        for (let col = 0; col < grid[row].length; col++) {
            if (grid[row][col] === '1') {
                count++;
                dfs(grid, row, col);
            }
        }
    }

    function dfs(grid, row, col) {
        if (row < 0 || row >= grid.length || col < 0 || col >= grid[row].length || grid[row][col] === '0') {
            return;
        }
        // 正确标记为已访问（淹没）
        grid[row][col] = '0';
        dfs(grid, row - 1, col);
        dfs(grid, row + 1, col);
        dfs(grid, row, col - 1);
        dfs(grid, row, col + 1);
    }

    return count;
}

额外优化：原代码中使用grid[0].length假设所有行的列数相同，改成grid[row].length更严谨；同时增加了空网格的判断，避免极端情况报错。

内容的提问来源于stack exchange，提问作者Udendu Abasili