一句话结论： 👉 BFS 本质上只和「队列（Queue）」有关。 它依赖 FIFO（先进先出）来保证节点按照“发现顺序”被处理，从而天然形成「一层一层」的遍历效果。 栈不参与 BFS 的任何核心逻辑。

⭐ 模板

层序遍历

  1. 初始化

    // 队列：保存“等待被访问的节点”
    Deque queue = new ArrayDeque<>();

    // visited：防止重复访问（树可以不要）
    Set visited = new HashSet<>();

    // 如果题目有“层 / 步数 / 时间”
    int step = 0;

    // 起点入队
    queue.offer(start);
    visited.add(start); // 入队即标记

  2. 遍历树

    while (!queue.isEmpty()) {

    int size = queue.size(); // 当前层节点数量

    // 这一轮，只处理这一层
    for (int i = 0; i < size; i++) {

    Node cur = queue.poll();

    // 1.当你真正走到这个节点时，要对它做的事（统计 / 判断 / 收集答案）
    process(cur);
    // 2. 扩展下一层节点
    for (Node next : neighbors(cur)) {
    if (!visited.contains(next)) {
    queue.offer(next); // 进队
    visited.add(next); // 立刻标记
    }
    }

    }

    // 一层处理完
    step++;
    }

  3. 返回结果

return res;

Questions

  1. visited 的使用

只有图/网格才需要使用 visited,树不需要

等待补充……

相关练习题

LeetCode 104. 二叉树的最大深度

题意： 给定一个二叉树 root ，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

LeetCode 111. 二叉树的最小深度

题意： 给定一个二叉树 root ，返回其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数。

LeetCode 200. 岛屿数量

题意： 给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

LeetCode 994. 腐烂的橘子

**题意：**在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

LeetCode 542. 01 矩阵

题意： 给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。两个相邻元素间的距离为 1

LeetCode 1091. 二进制矩阵中的最短路径

题意： 给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

路径途经的所有单元格的值都是 0 。
路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
畅通路径的长度 是该路径途经的单元格总数。

LeetCode 127. 单词接龙

题意： 字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk：

每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。