核心就是利用队列
Q: 如何区分下一层?
A: 将当前队列中的所有节点进形扩散
框架
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
Queue<Node> q; // 核心数据结构
Set<Node> visited; // 避免走回头路
q.offer(start); // 将起点加入队列
visited.add(start);
int step = 0; // 记录扩散的步数
while (q not empty) {
int sz = q.size();
/* 将当前队列中的所有节点向四周扩散 */
for (int i = 0; i < sz; i++) {
Node cur = q.poll();
/* 划重点：这里判断是否到达终点 */
if (cur is target)
return step;
/* 将 cur 的相邻节点加入队列 */
for (Node x : cur.adj()) {
if (x not in visited) {
q.offer(x);
visited.add(x);
}
}
}
/* 划重点：更新步数在这里 */
step++;
}
}
BFS 可以找到最短距离，但是空间复杂度高，而 DFS 的空间复杂度较低。
class Solution {
public:
int minDepth(TreeNode* root) {
if(root==nullptr) return 0;
queue<TreeNode*> que; //重点
set<TreeNode*> visited;
que.push(root); //根节点入队
int res = 1; //记录扩散的步数
while(!que.empty())
{
//扩散
int size = que.size(); //先记录下来,后面会变
for(int i = 0;i<size;i++)
{
TreeNode* temp = que.front();
//左子节点都空, 返回当前深度(根节点不算叶子节点)
if(temp->left==nullptr&&temp->right==nullptr) return res;
//否则左右子节点入队
if(temp->left!=nullptr) que.push(temp->left);
if(temp->right!=nullptr) que.push(temp->right);
//出队
que.pop();
}
//深度+
res++;
}
return res;
}
};