核心思想 & 框架

BFS 的核心思想：把一些问题抽象成树/图，从一个点开始，向四周开始扩散。
一般来说，我们写 BFS 算法都是用「队列」这种数据结构，每次将一个节点周围的所有节点加入队列。

从根节点逐层访问下一层节点，
在树的广度优先搜索里即层序遍历；在图的广度优先，要注意判重，有可能节点会被再次访问

BFS 相对 DFS 的最主要的区别是：BFS 找到的路径一定是最短的，但代价就是空间复杂度比 DFS 大很多
BFS 可以找到最短距离，但是空间复杂度高，而 DFS 的空间复杂度较低。

BFS 算法，队列中每次都会储存着二叉树一层的节点，这样的话最坏情况下空间复杂度应该是树的最底层节点的数量，也就是N/2，用 Big O 表示的话也就是O(N)。

一般来说在找最短路径的时候使用 BFS，其他时候还是 DFS 使用得多一些（主要是递归代码好写）

BFS 出现的常见场景：
图的广度优先搜索可以解决两类问题：
1、从节点A出发，有前往节点B的路径
2、从节点A出发，前往节点B的最短路径(限非加权图)
问题的本质就是让你在一幅「图」中找到从起点start到终点target的最近距离

广义的描述可以有各种变体，如

走迷宫，有的格子是围墙不能走，从起点到终点的最短距离是多少？如果这个迷宫带「传送门」可以瞬间传送呢？
两个单词，要求你通过某些替换，把其中一个变成另一个，每次只能替换一个字符，最少要替换几次？
连连看游戏，两个方块消除的条件不仅仅是图案相同，还得保证两个方块之间的最短连线不能多于两个拐点。你玩连连看，点击两个坐标，游戏是如何判断它俩的最短连线有几个拐点的？

大概分为两个场景：树、图；区别在于图较于树的访问，可能会产生由于回溯而导致的节点重复访问，所以需要visited空间记录已访问过的节点，防止走冤枉的重复路；

框架：

function BFS(startNode, endNode){
    let queue = [];
    let visited = new Map();
    queue.add(startNode);
    visited.set(startNode,1);
    let step = 0; // 扩散的步数
    while(queue.length){
        let prevLen = queue.length;
        # 拿到上层所有节点，齐头并进的 一并被访问；
          while(prevLen--) {
          let node = queue.shift();
            // 处理当前访问的节点
          // process(node);
          // 是否到达了终点
          if (node === endNode) {
              return step;
          }
          /* 将 cur 的相邻节点加入队列 */
          for(let nextnode in node.siblings) {
              // 在邻近节点筛选出没被访问过的
              if (!visited.get(nextnode)) {
                  queue.push(nextnode);
                  visited.set(nextnode, 1);
              }
          }
        }
        // 更新步骤
        step++;
    }
}

在树的广度优先搜索里即层序遍历：(简化版BFS)
=>

function levelOrder(root){
    if(!root) return [];
    let result = [];
    let queue = [root];

    while(queue.length){
        let prevLevelLen = queue.length;
        let curRes = [];// 存放上层全部节点

        while(prevLevelLen--){
            let node = queue.shift();
            curRes.push(node.val);
              // 将 cur 的相邻节点加入队列
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        result.push(curRes);
    }

    return result;
}

实例: 二叉树高度

问题：求root节点到叶子节点的最短路径上的节点个数(LeetCode 第 111 题)

最小高度

function minDepth(root){
    if(!root) return 0;
    let queue = [root];
    let level = 1;
    while(queue.length){
        let len = queue.length;
        while(len--){
            let node = queue.shift();

              # 按层访问，所以遇到第一个叶子节点 就直接return了，此时即是最小深度
              if (node.left === null && node.right === null) {
                return level;
            }

            node.left&&queue.push(node.left)
            node.right&&queue.push(node.right);            
        }

        level++
    }
    return level;
}

最大高度度：

function maxDepth(root){
    if(!root) return 0;
    let queue = [root];
    let level = 1;
    while(queue.length){
        let len = queue.length;
        while(len--){
            let node = queue.shift();
            node.left&&queue.push(node.left)
            node.right&&queue.push(node.right);            
        }
        if(queue.length) level++;
    }
      # 所有节点访问完了才知道最大的
    return level;
}

参考

BFS 算法框架套路详解

🤔数据结构与算法

BFS-广度优先遍历

核心思想 & 框架

实例: 二叉树高度

参考