Binary Tree BFS (广度优先搜索)

在数据结构与算法（DSA）中，Binary Tree BFS（广度优先搜索）是一种遍历二叉树的方法，和DFS（深度优先搜索）不同，BFS是从树的最上层开始，按层级逐层访问树中的节点。

什么是BFS？

• BFS全称“Breadth-First Search（广度优先搜索）”，其基本思想是：从树的根节点开始，先访问根节点，再访问根节点的所有直接子节点，然后是这些子节点的子节点，依此类推，层层向下遍历，直到树的所有节点都被访问到。

什么是二叉树？

• 二叉树是一种特殊的树结构，每个节点最多有两个子节点，通常是“左子节点”和“右子节点”。

Binary Tree BFS的工作原理

BFS通过队列（Queue）来实现，队列的特点是先进先出（FIFO），这使得BFS可以按层级顺序访问节点。具体过程如下：

1. 从根节点开始：首先将根节点放入队列中。
2. 访问队列中的节点：取出队列中的第一个节点（即当前层的节点），访问它。
3. 加入子节点：将该节点的左子节点和右子节点（如果有的话）依次加入队列。
4. 重复操作：重复步骤2和步骤3，直到队列为空，意味着所有节点都被访问过。

举个例子：

假设我们有一棵二叉树如下：

      1
     / \
    2   3
   / \
  4   5

1. 初始化队列：队列中先放根节点 1，队列为 [1]。
2. 访问根节点 1：从队列中取出 1，访问它，然后将它的子节点 2 和 3 加入队列，队列变成 [2, 3]。
3. 访问节点 2：从队列中取出 2，访问它，然后将它的子节点 4 和 5 加入队列，队列变成 [3, 4, 5]。
4. 访问节点 3：从队列中取出 3，访问它，队列变成 [4, 5]。
5. 访问节点 4：从队列中取出 4，访问它，队列变成 [5]。
6. 访问节点 5：从队列中取出 5，访问它，队列为空，遍历结束。

结果：

按照BFS的顺序，访问节点的顺序是：1 -> 2 -> 3 -> 4 -> 5。

总结：

• BFS是一种按层级遍历树的方式，逐层访问每一层的节点，直到所有节点都被访问过。
• BFS通常使用队列来实现，队列保证了层级的顺序，确保每一层的节点都在上一层的节点之后被访问。
• BFS适用于求解最短路径、层次遍历等问题，非常直观和有序。

LeetCode 相关题目:

LeetCode 二叉树 BFS 问题列表

已完成题目:

• 100. Same Tree
• 102. Binary Tree Level Order Traversal
• 107. Binary Tree Level Order Traversal II
• 111. Minimum Depth of Binary Tree
• 199. Binary Tree Right Side View
• 417. Pacific Atlantic Water Flow
• 1302. Deepest Leaves Sum