BFS 的把问题抽象成图，从一个点开始，向四周开始扩散。一般来说，我们写 BFS算法都是用「队列」这种数据结构，每次将一个节点周围的所有节点加入队列。
BFS 相对 DFS 的最主要的区别是：BFS 找到的路径一定是最短的，但代价就是空间复杂度比 DFS大很多。
模板（改编自LABULADONG的算法小抄）
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
Queue<Node> q; // 核心数据结构 队列
Set<Node> visited; // 避免走回头路
q.push(start); // 将起点加入队列
visited.add(start);
int step = 0; // 记录扩散的步数
while (!q . empty()) {
int sz = q.size();
/* 将当前队列中的所有节点向四周扩散 */
for (int i = 0; i < sz; i++) {
Node cur = q.front();
q.pop();//用完就丢
/* 划重点：这里判断是否到达终点 */
if (cur is target)
return step;
/* 将 cur 的相邻节点加入队列 */
for (Node x : cur.adj())
if (x not in visited) {
q.push(x);
visited.add(x);
}
}
/* 划重点：更新步数在这里 */
step++;
}
}
leetcode111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode* root) {
if(root==nullptr)
{
return 0;
}
queue<TreeNode*> q;
q.push(root);
int depth=1;
while(!q.empty())
{
int size=q.size();
for(int i=0;i<size;i++)
{
TreeNode *cur=q.front();//用一个丢一个，先进先出
q.pop();
if(cur->left==nullptr&&cur->right==nullptr)//结束搜索时机
{
return depth;
}
if(cur->left)//
{q.push(cur->left);
}
if(cur->right)
{q.push(cur->right);
}
}
depth++;//注意每一轮的深度是一样的，一轮结束后再增加深度
}
return depth;
}
};