队列与 BFS：层序遍历模板

Queue 在 BFS 中的作用

BFS（广度优先搜索）如同水波扩散——从起点出发，先访问所有距离为 1 的邻居，再访问距离为 2 的……队列的 FIFO 特性正好实现了这一「按层推进」的过程。

层序遍历（LeetCode 102）

最常见的 BFS 场景：二叉树按层遍历。

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;

    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    while (!q.isEmpty()) {
        int size = q.size();      // ← 当前层节点数（记下来！）
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            level.add(node.val);
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        res.add(level);
    }
    return res;
}

关键：记录每层大小。在 while 循环开始时记下 q.size()，用 for 循环只处理这一层，新入队的都是下一层。

{
  "type": "tree-traversal",
  "title": "层序遍历二叉树",
  "steps": [
    {
      "note": "初始：队列=[root=3]，第0层开始",
      "treeNodes": [
        {"id": 1, "val": 3, "left": 2, "right": 3},
        {"id": 2, "val": 9, "left": null, "right": null},
        {"id": 3, "val": 20, "left": 4, "right": 5},
        {"id": 4, "val": 15, "left": null, "right": null},
        {"id": 5, "val": 7, "left": null, "right": null}
      ],
      "visitedNodes": [],
      "activeEdge": null
    },
    {
      "note": "处理第0层：dequeue 3，入队 9 和 20。结果：[[3]]",
      "treeNodes": [
        {"id": 1, "val": 3, "left": 2, "right": 3},
        {"id": 2, "val": 9, "left": null, "right": null},
        {"id": 3, "val": 20, "left": 4, "right": 5},
        {"id": 4, "val": 15, "left": null, "right": null},
        {"id": 5, "val": 7, "left": null, "right": null}
      ],
      "visitedNodes": [1],
      "activeEdge": [1, 2]
    },
    {
      "note": "处理第1层：dequeue 9(无子节点)，dequeue 20(入队15和7)。结果：[[3],[9,20]]",
      "treeNodes": [
        {"id": 1, "val": 3, "left": 2, "right": 3},
        {"id": 2, "val": 9, "left": null, "right": null},
        {"id": 3, "val": 20, "left": 4, "right": 5},
        {"id": 4, "val": 15, "left": null, "right": null},
        {"id": 5, "val": 7, "left": null, "right": null}
      ],
      "visitedNodes": [1, 2, 3],
      "activeEdge": [3, 4]
    },
    {
      "note": "处理第2层：dequeue 15，dequeue 7。结果：[[3],[9,20],[15,7]]",
      "treeNodes": [
        {"id": 1, "val": 3, "left": 2, "right": 3},
        {"id": 2, "val": 9, "left": null, "right": null},
        {"id": 3, "val": 20, "left": 4, "right": 5},
        {"id": 4, "val": 15, "left": null, "right": null},
        {"id": 5, "val": 7, "left": null, "right": null}
      ],
      "visitedNodes": [1, 2, 3, 4, 5]
    }
  ]
}

层序遍历的变体

锯齿形层序（LeetCode 103）

奇数层从左到右，偶数层从右到左：

List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    boolean leftToRight = true;

    while (!q.isEmpty()) {
        int size = q.size();
        LinkedList<Integer> level = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (leftToRight) level.addLast(node.val);
            else level.addFirst(node.val);   // 反向插入
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        res.add(level);
        leftToRight = !leftToRight;
    }
    return res;
}

二叉树最小深度（LeetCode 111）

BFS 找最短路，第一次遇到叶子节点就是最小深度：

int minDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    int depth = 0;

    while (!q.isEmpty()) {
        depth++;
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (node.left == null && node.right == null) return depth;  // 叶子！
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
    }
    return depth;
}

图的 BFS（LeetCode 994 腐烂的橘子）

多源 BFS：同时从多个起点出发，求感染所有好橘子的最短时间。

int orangesRotting(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    Queue<int[]> q = new LinkedList<>();
    int fresh = 0;

    // 多源起点：所有烂橘子同时入队
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) q.offer(new int[]{i, j});
            if (grid[i][j] == 1) fresh++;
        }
    }

    int minutes = 0;
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    while (!q.isEmpty() && fresh > 0) {
        minutes++;
        int size = q.size();
        for (int i = 0; i < size; i++) {
            int[] pos = q.poll();
            for (int[] d : dirs) {
                int ni = pos[0] + d[0], nj = pos[1] + d[1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 1) {
                    grid[ni][nj] = 2;
                    fresh--;
                    q.offer(new int[]{ni, nj});
                }
            }
        }
    }
    return fresh == 0 ? minutes : -1;
}

BFS vs DFS

一句话记忆：BFS 先宽后深（层序）；DFS 先深后回（递归）。