壹 ? 引

我在一文中，从一个最基本的数组遍历引出递归，在掌握递归的书写规则后，又从JS执行栈角度解释了二叉树三种深度优先（前序、中序后序）的底层差异，帮助大家站在模板的角度上深入理解模板。而二叉树还剩一种广度优先（也称层序遍历）也使用广泛，但考虑到篇幅问题，所以还是打算另开一篇文章讲解。

其实相对深度优先，广度优先的模板要好理解的一些，毕竟它没有让人头疼的递归，且我们只用维护好一个队列queue（先进先出）即可，但考虑到刚接触算法人基础不同，我们还是用图解以及更直白的话术来讲解层序遍历的模板，那么本文开始。

贰 ? 壹 从队列与栈说起

其实通过前文二叉树深度遍历的讲解，所谓前序、中序与后序遍历的差异，本质上是将做一件事的动作放在了递归前后不同位置，而这个原理其实依赖了JS执行栈先进后出的特性，这是JS底层帮我们做的事。那我们自己能不能模拟栈呢？显然是可以的，通过数组的push与pop方法，比如数字1 2 3我可以先全部push到一个空数组中变成[1, 2, 3]，然后再利用pop依次弹出就能倒序访问变成3 2 1。

const stack = [];
// 先进
stack.push(...[1, 2, 3]);

while (stack.length > 0) {
  // 后出
  console.log(stack.pop());// 3 2 1
}

用图来表示这个过程：

而栈的特性是先进后出，我们是不是一样可以用数组模拟这个过程，别忘了数组还有shift方法：

const queue = [];
queue.push(...[1, 2, 3]);

while (queue.length > 0) {
  console.log(queue.shift()); // 1 2 3
};

理解了用数组模拟队列的过程，那么层序遍历就理解了一半了。

叁 ? 图解层序遍历

我们来看一个最基本的二叉树层序遍历例子，如下，如果要层序遍历输出自然是[1,2,3,4,5,6,7]，那么怎么做？

固定套路，我们可以先定义一个承装结果的数组ans，以及一个模拟队列的数组queue，整个遍历的过程都会检查queue的长度，只要length > 0证明还有元素，那就标明可以继续做我们要做的事。

很明显面对上图的二叉树，第一次层自然是根节点，那我们就可以将根节点先塞到queue中：

然后开始遍历queue做我们要做的操作，做什么呢？当然是将当前节点的值存起来，之后因为节点1已经访问过了，遵循先进先出的特性，我们需要将1从数组头部弹出。那么问题来了，1要是弹出queue长度直接为0遍历结束，但我们希望继续检查第二层，我们是不是得将1的子节点依次也push到queue中，于是就有了下面这一步，将2 3入队列，并将1弹出：

同理，因为当前queue长度为2，很明显我们能继续遍历，依次将2,3存入ans数组，之后再将2的子节点4,5与3的子节点6,7存入queue，同时2,3出队列。

之后我们再将4,5,6,7的值存入ans，但由于这四个节点没有自己的子节点，所以我们只用让它们四个出队列，也由于没有新的节点进来，queue长度为空，终于整个查找过程结束，我们顺序得到ans [1,2,3,4,5,6,7]。

在通过图解解释了这个过程后，我们就能很清晰定义出层序遍历的模板：

const levelTraverse = (root) => {
  if (root === null) return;
  const queue = [];
  const ans = [];
  queue.push(root);
  // 当队列为空时跳出遍历
  while (queue.length > 0) {
    // 当前节点出队列
    const node = queue.shift();
    // 做你要做的操作
    ans.push(node.val);
    // 别忘了让node的左右子节点进入队列
    // 因为不是递归了，加入前还是有必要检查有没有子节点
    if (node.left !== null) {
      queue.push(node.left);
    }
    if (node.right !== null) {
      queue.push(node.right);
    }
  };
  return ans;
}

肆 ? 一道基础的层序遍历面试题

那么图解完层序遍历模板，我们趁热打铁来做道题。我现在公司有一个同事一直负责他们部门的前端招聘工作，有一次他跟我说今天一个来面试候选人有点厉害，算法10分钟就写出来了，我出于兴趣就问他考的什么算法题？于是他就把题目发给我了，题目如下：

// 从后端拿到了一个文档节点树结构，请按广度优先遍历（BFS）的顺序，返回该树结构的所有节点名字。
// 树节点列表的数据说明：

// 节点定义
const NodeType = {
  name: '