有迹可循的 BFS 问题 | 创作者训练营

BFS（Breadth First Search）广度优先算法

问题

LeetCode 102 二叉树层序遍历

分析

按层打印，如何换行就是首先要关心的问题。

根节点是明确的，同时根节点又是下一层的入口（通过 root.left / root.right 带出）。所以我们需要一个队列（queue）储存当前层所有的节点。每次换行，将上一层的节点推到结果数组中，并且通过递归收集当前层所有的节点，直到最后一层 - 队列为空。

换行的细节，将 queue 中的一个 node 出队，同时将这个 node 的左右节点入队。直到 queue 中上一层所有的节点全部出队完毕，此时下一层所有节点也全部入队啦。依次递归，直到 queue 为空。

节点为空为整个递归的结束条件。

实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
const levelOrder = (root) {
  if(!root) return [];
  
  // 起始状态
  // 递归入口
  const queue = [root];
  let res = [];
  
  // 开始遍历队列
  // 1. 循环终止条件为 queue.length
  while(queue.length) {
    // 2. 遍历 queue 时的终止条件用变量保存了一下
    //    这样做和不保存有什么区别
    //    如果和 1 处做个交换会怎么样
    const len = queue.length;
    for(let i=0; i < len; i++) {
      // 当前层（queue）的节点全部出队列
      // 并把下一层的节点全部入队
      const node = queue.shift();
      curlevel.push(node.val);
      if(node.left) queue.push(node.left);
      if(node.right) queue.push(node.right);
    }
    
    res.push(curlevel);
  }
  
  return res; 
}

总结

BFS 中需要关注充当中间状态转换的队列（queue），以队列为突破口。关注换层的迭代过程。

同时思考下代码注释中 1 、2 处有什么不同呢？

「 一枚前端学习小透明，努力学习前端知识，同时分享自己对生活的一些思考，欢迎一起讨论交流。如果我的文章对你有帮助，请点个赞，会非常感恩你的鼓励。完」

创作者训练营 征文活动正在进行中......