Hot 100 --- 岛屿数量

本文概览：本文以LeetCode题目"岛屿数量"为例，从二叉树的递归视角迁移到二维网格的四方向递归，讲解DFS和BFS两种标记岛屿的方法

一、题目

岛屿数量题目

二、题目分析

题目要求：给定一个二维网格，计算岛屿的数量。'1' 代表陆地，'0' 代表水

什么是岛屿？这是这题最容易让人困惑的地方。岛屿的定义是：对于某个 '1'，它的上下左右如果也是 '1'，就属于同一个岛屿。但如果斜着的 '1'，则不属于这个岛屿的一部分

看下面这个例子：

1 2	1 1 0 1 0 1

左上角的三个 1：左上和右上是横向相邻（连通），左上和左下是纵向相邻（连通），所以这三个 1 属于同一个岛屿
右下角的 1：和左下的 1 是斜着相邻，但斜方向不算连通，所以它是一个独立的岛屿

最终这个网格有 2 个岛屿。关键就是：只有上下左右方向相邻的 1 才算连通，斜方向不算

理解了岛屿的定义后，这题其实和前面做过的二叉树是同一个套路：

	二叉树	二叉网格
从当前节点出发的方向	左、右	上、下、左、右
遍历方式	递归左右子树	递归上下左右
防止重复访问	天然有向（父→子）	需要手动标记

二叉树从父节点往子节点走，天然不会走回去。但二维网格四个方向走来走去，会重复访问同一个格子，所以必须标记已访问的格子

整体思路：遍历整个网格，每遇到一个新的 '1'，就代表发现了一个新岛屿，count+1，然后把这个岛屿的所有陆地都标记掉（变成 '0'），以后再遍历到就不算了。标记的方法有两种：DFS 和 BFS

思路概览

方法一：DFS

class Solution {
    // 岛屿数量
    private int count = 0;

    // 上下左右
    private final int[][] dirs = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};

    // 长宽
    private int rows, cols;

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 ) {
            return 0;
        }
        rows = grid.length;
        cols = grid[0].length;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == '0') {
            return;
        }
        // 标记为已访问过
        grid[i][j] = '0';
        
        // 递归访问上下左右
        for (int[] dir : dirs) {
            int newRow = i + dir[0];
            int newCol = j + dir[1];
            dfs(grid, newRow, newCol);
        }
    }
}

方法二：BFS

class Solution {
    // 岛屿数量
    private int count = 0;

    // 上下左右
    private final int[][] dirs = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};

    // 长宽
    private int rows, cols;

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        rows = grid.length;
        cols = grid[0].length;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    bfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    private void bfs(char[][] grid, int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        // 入队时就标记，防止重复加入
        grid[i][j] = '0';
        queue.offer(new int[]{i, j});

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int row = cur[0];
            int col = cur[1];
            // 遍历上下左右
            for (int[] dir : dirs) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];
                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols
                        && grid[newRow][newCol] == '1') {
                    // 入队时就标记为已访问
                    grid[newRow][newCol] = '0';
                    queue.offer(new int[]{newRow, newCol});
                }
            }
        }
    }
}

思路简要说明

两种方法的外层逻辑完全一样：遍历网格，遇到 '1' 就 count+1 并把整个岛屿标记掉。区别只在标记岛屿的方式：

DFS：遇到 '1'，递归它的上下左右，一路走到头，和二叉树的先序遍历一个道理
BFS：遇到 '1'，把它周围的 '1' 全部加入队列，一层层往外扩散
BFS 的关键细节：标记时机必须是入队时，不是出队时。如果出队才标记，同一个格子会被重复加入队列，导致死循环

三、思路详解

第一步：从二叉树到二维网格

前面做了很多二叉树的题目，核心就是从一个节点出发，递归访问它的左右子树。这题其实是一样的思路，只是方向从 2 个变成了 4 个：

二叉树（2个方向）：        二维网格（4个方向）：

    节点                      上
   /      \                  |
  左       右            左 — (i,j) — 右
                              |
                             下

二叉树的递归模板：

private void dfs(TreeNode node) {
    if (node == null) return;       // 出口
    // 处理当前节点
    dfs(node.left);                 // 递归左
    dfs(node.right);                // 递归右
}

二维网格的递归模板：

private void dfs(char[][] grid, int i, int j) {
    if (越界 || grid[i][j] == '0') return;   // 出口
    grid[i][j] = '0';                          // 标记已访问
    // 递归上下左右
    for (int[] dir : dirs) {
        dfs(grid, i + dir[0], j + dir[1]);
    }
}

结构完全一样，区别只有两点：出口条件多了"越界判断"，以及递归前多了一步"标记已访问"

第二步：为什么需要标记？

二叉树从父节点往子节点走，是单向的，天然不会走回去。但二维网格四个方向是互相的——你从 (0,0) 走到 (0,1)，(0,1) 的左边方向又指回 (0,0)，如果不标记就会无限来回走

不标记的情况：

(0,0) → 访问右边 (0,1)
(0,1) → 访问左边 (0,0)  ← 又回去了！
(0,0) → 访问右边 (0,1)  ← 又回来了！
... 死循环

所以每次访问一个格子，必须立刻把它变成 '0'，这样后续任何方向走到这里都会直接 return

第三步：DFS 标记过程图解

以这个 4×5 网格为例：

遍历到 (0,0)，发现 '1'，count=1，开始 DFS 标记

① 访问 (0,0)，标记为 '0'，递归上下左右

  [0] 1 0 0 0      ← (0,0) 标记
   1  1 0 0 0

② 上越界，下到 (1,0)，标记为 '0'

  [0] 1 0 0 0
  [0] 1 0 0 0      ← (1,0) 标记

③ (1,0) 的下越界，左越界，右到 (1,1)，标记为 '0'

   0  1 0 0 0
  [0][0]0 0 0      ← (1,1) 标记

④ (1,1) 的上是 (0,1)，标记为 '0'

  [0][0]0 0 0      ← (0,1) 标记
   0 [0]0 0 0

⑤ (0,1) 的上下左右要么越界要么是 '0'，递归结束

标记后的网格：
  0 0 0 0 0
  0 0 0 0 0
  0 0 1 0 0
  0 0 0 1 1

继续遍历到 (2,2)，发现 '1'，count=2，DFS 标记它（单个格子）

继续遍历到 (3,3)，发现 '1'，count=3，DFS 标记 (3,3) 和 (3,4)

最终 count = 3

第四步：BFS 标记过程图解

BFS 的思路不是一路走到头，而是一层层往外扩散。以 (0,0) 为例：

初始：
  [1] 1 0 0 0     ← (0,0) 入队并标记为 '0'
   1  1 0 0 0

第一轮：出队 (0,0)，把周围的 '1' 入队并标记

  [0][1]0 0 0     ← (0,1) 入队标记
  [1] 1 0 0 0     ← (1,0) 入队标记
  队列：[(0,1), (1,0)]

第二轮：出队 (0,1)，周围没有未标记的 '1'
        出队 (1,0)，把 (1,1) 入队并标记

   0 [0]0 0 0
  [0][1]0 0 0     ← (1,1) 入队标记
  队列：[(1,1)]

第三轮：出队 (1,1)，周围没有未标记的 '1'

队列为空，BFS 结束

第五步：BFS 的关键细节——入队时标记还是出队时标记？

这是 BFS 写法里最容易踩坑的地方

错误写法（出队时标记）：

// ❌ 错误：出队时才标记
while (!queue.isEmpty()) {
    int[] cur = queue.poll();
    grid[cur[0]][cur[1]] = '0';   // 出队才标记
    for (int[] dir : dirs) {
        int newRow = cur[0] + dir[0];
        int newCol = cur[1] + dir[1];
        if (越界判断 && grid[newRow][newCol] == '1') {
            queue.offer(new int[]{newRow, newCol});
            // 没有标记！
        }
    }
}

为什么错？看这个例子：

初始：queue = [(0,0)]，grid[0][0] 还是 '1'

第一轮：出队 (0,0)，标记为 '0'
  检查周围，发现 (0,1) 和 (1,0) 是 '1'，加入队列
  queue = [(0,1), (1,0)]

第二轮：出队 (0,1)，标记为 '0'
  检查周围，发现 (1,1) 是 '1'，加入队列
  同时 (0,0) 已经是 '0' 了，跳过
  queue = [(1,0), (1,1)]

第三轮：出队 (1,0)，标记为 '0'
  检查周围，(0,0) 是 '0' 跳过
  但 (1,1) 还是 '1'！（还没出队，没被标记）
  于是又把 (1,1) 加入队列！
  queue = [(1,1), (1,1)]  ← 重复了！

同一个格子被加入队列多次，每个出队时又会把周围的 '1' 加入队列，最终导致死循环

正确写法（入队时标记）：

1
2
3

// ✅ 正确：入队时就标记
grid[newRow][newCol] = '0';    // 入队前立刻标记
queue.offer(new int[]{newRow, newCol});

入队时就标记成 '0'，后面其他格子检查到它时看到的是 '0'，就不会重复加入了。一个格子只会入队一次，不会死循环

第六步：DFS vs BFS 对比

	DFS	BFS
数据结构	递归栈	队列
标记时机	进入函数立即标记	入队时立即标记
遍历顺序	一路走到头，再回溯	一层层往外扩散
空间复杂度	O(rows×cols) 最坏递归深度	O(rows×cols) 最坏队列长度
效果	完全一样	完全一样

两种方法只是标记岛屿的遍历方式不同，最终都能把同一个岛屿的所有陆地标记掉，不影响 count 的计算

复杂度分析

时间复杂度：O(rows×cols)，每个格子最多被访问一次
空间复杂度：O(rows×cols)，DFS 最坏递归深度，BFS 最坏队列长度