概述
BFS：广度优先搜索，通常用来求最短距离
以二叉树的最小高度为例：
- 从根节点开始
- 一层一层扩散，并记录高度信息
- 直到遇到叶子节点结束，返回高度信息
框架
伪代码：
// 计算从起点 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++;
}
}
核心数据结构：
- Queue，缓存当前层节点的队列
- Set，记录节点访问历史的集合，不会走回头路的情况，可忽略
练习
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
return bfs(root);
}
private int bfs(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int depth = 1;
while (!queue.isEmpty()) {
int sz = queue.size();
for (int i=0; i<sz; i++) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null) {
return depth;
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
depth++;
}
return depth;
}
}
参考
- https://labuladong.gitee.io/algo/4/29/111/