1. BFS/DFS区别
- BFS找到的路径一定是最短
- BFS的空间复杂度比DFS大很多
2. 如何判断是BFS
- 在一个图中，找起点到终点的最短距离
- 二叉树也可以理解为1个图
2. BFS步骤
重点是【当前队列】
概念：
- 当前队列：需要向外扩展的数据，
- 已访问列表：避免走回头路。（二叉树没有子到父的指针，一般不需要已访问列表）
- 扩散步数：记录距离（这个一般为答案）
步骤：
- 【起点】推入当前队列
- 当前队列的点向外扩散
- 判断是否抵达【终点】，抵达则返回扩散步数
未抵达，则将当前点所有邻点推入当前队列 - 一轮扩散完毕后，扩散步数更新
3. BFS框架
js
function BFS(start, target) {
var q = [] // 当前队列
var visited = new Set() // 已访问列表
q.push(start) // 起点加入当前队列
visited.add(start)
var step = 0 // 记录扩散步数
while( q.length) {
var length = q.length // 记录当前队列长度
/* 当前队列中的所有节点向外扩散 */
for (var i = 0; i < length; ++i) {
var cur = q.shift()
/* 划重点，判断是否抵达终点 */
if(cur === target) {
return step
}
/* 将当前点所有邻点加入当前队列 */
for(邻点 of 所有邻点) {
if (visited.includes(邻点)) continue
q.push(邻点)
visited.add(邻点)
}
}
/* 划重点，步数更新 */
step++
}
}
4. 细化问题点
4.1 时间复杂度低，O(N)
根据其框架逻辑，循环一次depth增加一次，找到终点时能保证距离最短。最坏情况下在满二叉树时，从根节点起点，找底层最后一个树节点时，就需要全部节点穷举过，所以是O(N) DFS也是O(N)，但永远都是需要所有分叉都走完才能对比，实际比BFS慢很多。BFS是面，DFS是线。BFS是集体行动，DFS是单打独斗。
4.2 空间复杂度高，为O(N)
空间复杂度为O(N)。最坏情况下在满二叉树时，存了最底部的树节点N/2，所以最坏空间复杂度O(N)。而DFS是递归，是一条线，最坏情况下也是树的高度，即O(logN)
4.3 双向BFS-优化
从起点和终点同时扩散，相遇（有交集）时停止。最坏时还是O(N)，但实际中，如果是起点根节点，满二叉树底部的中间终点，便只要遍历半棵树。
总结
- BFS与DFS
- BFS的实际时间复杂度低，但空间复杂度高，而DFS相反。
- 时间复杂度
BFS: O(N)
DFS: O(N) - 空间复杂度
BFS: O(N)
DFS: O(logN)