labuladongBFS算法解题套路框架
BFS通常用于找到最短路径
- BFS算法的框架：
- 用队列存储数据。将父节点（比如a,b,c）放入队列
- 依次判断当前的（父）节点是不是需要找的点（并存入visited中）
- 如果是，则返回结果
- 如果不是，则将当前的（父）节点加入队列中 （并更新扩散的步数），等待后续判断
- 依次判断当前的（父）节点是不是需要找的点（并存入visited中）
- 注意：要在for循环里面判断cur是否为目标。因为在for循环中，一次放一批节点（比如a,b,c）。在判断并弹出节点时，abc是相同的“地位”，因此都要在for循环里判断
- 用visited记录已经走过的路，防止跳入死循环
- 用队列存储数据。将父节点（比如a,b,c）放入队列
// 计算从起点 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++;
}
}111. 二叉树的最小深度
方法1：BFS
- 因为这是一个二叉树，始终向下走，所以不用担心它会遍历到重复的节点，不需要用visited记录已访问的节点
class Solution {
public:
int minDepth(TreeNode *root) {
// 初始化：若不存在节点，则返回0，否则把节点添加到队列中，深度为自己的1
if (root == nullptr) return 0;
queue < TreeNode * > q;
q.push(root);
int depth = 1;
while (!q.empty()) {
int sz = q.size();
// 当前队列对应的相邻节点向四周扩散
for (int i = 0; i < sz; ++i) {
// 判断当前节点是否满足结束条件
TreeNode *cur = q.front();
q.pop(); // 这里切记要更新队列。pop出节点，否则队列始终不为空，跳不出while循环
if (cur->left == nullptr && cur->right == nullptr) return depth;
// 若不满足，则将相邻节点添加到队列
if (cur->left != nullptr) q.push(cur->left);
if (cur->right != nullptr) q.push(cur->right);
}
depth += 1;
}
return depth;
}
};
方法2：递归
- 递归结束的条件或者特判：若是空节点，则返回0
- 若左右孩子都为空：返回1
- 若左右孩子有一个为空：返回非空孩子的递归结果+1
- 否则都不为空，返回左右孩子递归结果的最小值+1
注意：
在求最大深度时，可以通过代码直接求max:class Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ def dfs(root): if not root: return 0 l=dfs(root.left) r=dfs(root.right) return max(l,r)+1 return dfs(root)与最大深度不同的是，在求最小深度时，不能直接返回
1 + min(l, r)。要添加：如果有一个孩子，要返回1+这个孩子的深度
- 比如1的左子树为2，右子树为None。以2为根节点的最小深度为1，以None为根节点的最小深度为0. 则对于根节点1而言，最小深度为1（自己）+1（根节点2返回的结果）。也就是说：
- 当左右子树都存在时，返回
1 + min(l, r)（e.g., 2和3，返回1+最小值（2））- 当左右子树只有一个存在时，返回
1+存在子树的结果（e.g., 0和2，返回1+存在值（2））# 如果左子树为空，右子树不为空，说明最小深度是1 + 右子树的深度 if l==0 and r!=0: return 1+r # 如果右子树为空，左子树不为空，说明最小深度是1 + 左子树的深度 if r==0 and l!=0: return 1+l
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
# 递归结束的条件
if not root:
return 0
l = minDepth(root.left)
r = minDepth(root.right)
# 如果左子树为空，右子树不为空，说明最小深度是1 + 右子树的深度
if l==0 and r!=0:
return 1+r
# 如果右子树为空，左子树不为空，说明最小深度是1 + 左子树的深度
if r==0 and l!=0:
return 1+l
# 如果左右子树都不为空，则返回1+min(l, r)
return 1 + min(l, r)
/**
* 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 (not root)
return 0;
int l = minDepth(root->left);
int r = minDepth(root->right);
if (l == 0 && r != 0)
// if (root->left ==NULL && root->right!= NULL)
return 1 + r;
if (r == 0 && l != 0)
return 1 + l;
return 1 + min(l, r);
}
};
