LeetCode BFS 刷题模板
内容提要
广度优先搜索（BFS）是一种用于树或图的搜索算法，主要通过队列实现。其基本步骤包括初始化队列、添加起始节点、循环遍历队列并处理节点及其邻居。BFS常用于求解最短路径、层级遍历和判断图中环路等问题。
延伸解读
BFS 与 DFS 的直观对比
文章用“不撞南墙不回头”形容 DFS，用“步步为营”形容 BFS，形象地指出两者探索策略的差异。BFS 依赖队列逐层扩展，适合寻找最短路径或层级遍历；DFS 则依赖递归或栈，适合深度优先的路径搜索。理解这一区别有助于在刷题时根据问题特性选择合适算法，避免盲目套用模板。
BFS 模板的通用性与调整要点
文章强调 LeetCode 中的 BFS 题目大多可在基础模板上添加具体逻辑。模板核心包括初始化队列、标记访问、循环出队、处理节点、遍历邻居并入队。针对不同问题，需调整的是节点处理逻辑和邻居生成方式，例如在岛屿问题中标记陆地，在克隆图中建立映射。掌握模板后，只需关注题目特有的处理步骤即可。
BFS 在二叉树中的复杂度分析
文章指出 BFS 在二叉树中的时间复杂度为 O(N)，空间复杂度为 O(W)，其中 W 为树的最大宽度。最坏情况下，如链表状二叉树，空间复杂度可能达到 O(N)。与 DFS 相比，两者时间空间复杂度相同，但 BFS 在层级遍历时更直观。了解复杂度有助于评估算法在极端情况下的表现。
典型题目的解题思路借鉴
文章通过岛屿数量、被围绕的区域、克隆图等图题目，以及二叉树最大深度、层平均值、根到叶数字之和等树题目，展示了 BFS 模板的具体应用。例如，被围绕的区域先标记边界连通的 O，再翻转剩余 O；根到叶数字之和需用额外队列保存路径值。这些思路可迁移到类似问题中，提升解题效率。
Q&A
广度优先搜索（BFS）是什么？
广度优先搜索（BFS）是一种在树或图中搜索满足条件的节点的算法，主要通过队列实现。
BFS的基本步骤有哪些？
BFS的基本步骤包括初始化队列、添加起始节点、循环遍历队列并处理节点及其邻居。
BFS常用于解决哪些问题？
BFS常用于求解最短路径、层级遍历和判断图中环路等问题。
BFS的时间复杂度和空间复杂度分别是多少？
BFS的时间复杂度为O(N)，空间复杂度为O(W)，其中N为节点个数，W为最大宽度。
在二叉树中，BFS可以用来解决哪些问题？
在二叉树中，BFS可以用于层级遍历、计算最大深度、求每层平均值等问题。
如何根据具体逻辑调整BFS算法模板？
在解决特定问题时，BFS算法的模板可以根据具体逻辑进行调整，例如处理节点时的操作。
