一、概念
1、定义
Broad First Search
2、与DFS区别
BFS找到的路径最短
3、本质
找出图中从起点到终点的最近距离
二、二叉树的最小高度111
1、代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
int depth = 1;
while(!q.isEmpty()){
int sz = q.size();
for(int i = 0; i < sz; i++){
TreeNode node = q.poll();
if(node.left == null && node.right == null)
return depth;
//将邻接点加入队列
if(node.left != null)
q.offer(node.left);
if(node.right != null)
q.offer(node.right);
}
depth++;
}
return depth;
}
}
2、比较
DFS靠递归的堆栈，BFS借助队列齐头并进
BFS可以在没遍历完整棵树时就得到最短距离，而回溯法必须遍历完整棵树才行
DFS空间复杂度log级（堆的深度=树高），BFS空间复杂度N
一般在寻找最短路径时用BFS，否则用DFS更多一些。
三、打开转盘锁752
class Solution {
String plusOne(String s, int i){
char[] str = s.toCharArray();
if(str[i] == '9'){
str[i] = '0';
}else{
//str[i] = (char)str[i] + 1;
str[i] += 1;
}
return new String(str);
}
String minusOne(String s, int i){
char[] str = s.toCharArray();
if(str[i] == '0'){
str[i] = '9';
}else{
str[i] -= 1;
}
return new String(str);
}
public int openLock(String[] deadends, String target) {
Set<String> deads = new HashSet<>();
for(String deadend : deadends) deads.add(deadend);
Set<String> visited = new HashSet<>();
Queue<String> q = new LinkedList<>();//双向BFS不需要栈，而是set即可
int step = 0;
q.offer("0000");
visited.add("0000");
while(!q.isEmpty()){
//如果是双向不需要出队，直接foreach遍历邻接节点
int sz = q.size();
for(int i = 0; i < sz; i++){
String cur = q.poll();//出队后的不再入队
//判断是否是终点
if(deads.contains(cur)){
continue;
}
if(cur.equals(target)){
return step;
}
for(int j = 0; j < 4; j++){
String up = plusOne(cur,j);
if(!visited.contains(up)){
visited.add(up);
q.offer(up);
}
String minus = minusOne(cur,j);
if(!visited.contains(minus)){
visited.add(minus);
q.offer(minus);
}
}
}
step++;
}
return -1;
}
}
可以使用双向BFS优化，循环开始选择小的分支进行轮转
