theme: awesome-green

前言

算法中二叉树的数据结构尤其重要，而二叉树除了常见的递归遍历之外，还有一个很重要的遍历方式--层序遍历，二叉树的基础在于遍历，可以说，熟练的掌握了二叉树的递归和层序遍历，二叉树的基础就打的很牢固了。

原题（LeetCode102）

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

准备工作

在想这道题目之前，我们应该了解一下：

1. JavaScript基础知识：你需要了解JavaScript的基本语法、数据类型、流程控制等，以及数组和对象的使用方法。
2. 数据结构和算法：理解树这种数据结构的基本概念，以及广度优先搜索（BFS）算法的原理。BFS 是一种图形搜索算法，用于遍历或搜索树或图的数据结构。在这段代码中，BFS 用于按层次遍历树的节点。
3. 二叉树：了解二叉树的基本概念，包括节点、左子树、右子树等。
4. JavaScript的数组和队列：理解数组和队列在JavaScript中的使用方式，包括数组的push和shift方法，队列的FIFO（先进先出）特性。
5. 递归：尽管这段代码没有使用递归，但理解递归对于理解树的遍历和递归解法也是有帮助的。
6. ES6语法：这段代码使用了ES6的语法，如const、箭头函数等，因此对ES6语法的了解也是必要的。

基本思路

1. 创建队列：首先，我们需要创建一个队列，用来存储待处理的节点。我们可以使用数组来模拟队列的功能。
2. 将根节点入队：将二叉树的根节点放入队列中。
3. 循环处理队列中的节点：进入一个循环，该循环将处理队列中的节点。循环条件是队列不为空。
4. 处理当前节点：在循环中，我们从队列中取出一个节点。这个节点是我们当前要处理的节点。
5. 存储节点值：将当前节点的值存储起来。这样，我们就记录了当前层次上的一个节点的值。
6. 将子节点入队：接下来，我们检查当前节点是否有左子节点和右子节点。如果有，就将它们依次放入队列中。这样，在下一轮循环中，我们就可以处理它们了。
7. 循环直到队列为空：重复执行步骤 4 到步骤 6，直到队列为空。这意味着我们已经处理完了整棵树的所有节点。
8. 返回结果：最后，我们得到的结果就是按层序遍历顺序存储的节点值的数组。

这种方法保证了我们按照从上到下、从左到右的顺序逐层遍历二叉树的节点，因此称为层序遍历。通过队列的先进先出特性，我们可以保证每一层的节点都会按照顺序被处理。在层序遍历二叉树中队列扮演了关键角色。队列的作用在于维护待处理的节点顺序，并确保按照层序逐个处理这些节点。 首先，我们将根节点放入队列中。然后，进入循环，不断从队列中取出节点进行处理。在处理当前节点时，我们将其值存储，并将其子节点（如果存在）按顺序放入队列中。这样，队列始终保持了待处理节点的正确顺序：每次取出的节点都是上一层节点的子节点，确保了按层遍历的顺序性。 队列的FIFO（先进先出）性质确保了节点按照层序逐个被处理，使得层序遍历能够有效地完成。

代码

var levelOrder = function(root) {
  // 初始化存储层序遍历结果的数组
  const arr = [];
  // 初始化队列，用于存储待处理的节点
  const queue = [];
  // 将根节点入队
  queue.push(root);
  // 若根节点为空，直接返回空数组
  if (!root) return arr;
  
  // 循环处理队列中的节点
  while (queue.length) {
      // 记录当前层节点的数量
      const l = queue.length;
      // 临时数组，用于存储当前层节点的值
      const c = [];
      // 处理当前层的所有节点
      for (let i = 0; i < l; i++) {
          // 取出队首节点
          const node = queue.shift();
          // 将节点值存入临时数组
          c.push(node.val);
          // 若当前节点有左子节点，将左子节点入队
          if (node.left) queue.push(node.left);
          // 若当前节点有右子节点，将右子节点入队
          if (node.right) queue.push(node.right);
      }
      // 将当前层节点值数组存入结果数组
      arr.push(c);
  }
  // 返回层序遍历结果数组
  return arr;
};

1. 首先，我们定义了一个函数 levelOrder，它接受一个参数 root，代表二叉树的根节点。
2. 创建了两个空数组 arr 和 queue，arr 用来存储层序遍历的结果，queue 用来存储待处理的节点。
3. 将根节点 root 入队 queue.push(root)。
4. 若根节点为空 if (!root)，直接返回空数组 return arr，表示二叉树为空，无需遍历。
5. 进入 while 循环，只要队列不为空，就一直执行遍历操作。
6. 在循环中，首先获取当前队列的长度 const l = queue.length，以确定当前层节点的数量。
7. 定义一个临时数组 c，用于存储当前层节点的值。
8. 使用 for 循环遍历当前层的所有节点，循环次数由当前队列的长度决定。
9. 在循环中，取出队首节点 const node = queue.shift()，并将其值存入临时数组 c.push(node.val)。
10. 如果当前节点有左子节点，将左子节点入队 if (node.left) queue.push(node.left)。
11. 如果当前节点有右子节点，将右子节点入队 if (node.right) queue.push(node.right)。
12. 将存储了当前层节点值的临时数组 c 存入结果数组 arr.push(c)，表示当前层节点已经遍历完毕。
13. 循环结束后，所有层的节点都已经遍历完成，将结果数组返回 return arr。

如果你还是没有看懂这段代码，没有关系，让我们来举一个具体的例子

实例说明

考虑以下这个二叉树：

        1
       / \
      2   3
     / \ / \
    4  5 6  7

对于这个二叉树，根节点是 1，它有左右两个子节点 2 和 3，而节点 2 又有左右子节点 4 和 5，节点 3 有左右子节点 6 和 7。

现在，我们来看看代码如何按层遍历这个二叉树：

1. 初始时，队列 queue 中只有根节点 1，结果数组 arr 为空。
2. 进入第一次循环，当前队列长度为 1。取出队首节点 1，将其值存入临时数组 c，并将节点 1 的左右子节点 2 和 3 入队。
3. 循环结束后，临时数组 c 中存储了当前层的节点值 [1]，将其存入结果数组 arr，此时 arr = [[1]]。
4. 进入第二次循环，当前队列长度为 2。取出队首节点 2 和 3，将它们的值存入临时数组 c，并将它们的子节点入队。
5. 循环结束后，临时数组 c 中存储了当前层的节点值 [2, 3]，将其存入结果数组 arr，此时 arr = [[1], [2, 3]]。
6. 进入第三次循环，当前队列长度为 4。取出队首节点 4、5、6、7，将它们的值存入临时数组 c，并将它们的子节点入队。
7. 循环结束后，临时数组 c 中存储了当前层的节点值 [4, 5, 6, 7]，将其存入结果数组 arr，此时 arr = [[1], [2, 3], [4, 5, 6, 7]]。
8. 因为队列已经为空，循环结束。整个二叉树的层序遍历完成，结果存储在数组 arr 中。

最终的结果数组 arr 为 [[1], [2, 3], [4, 5, 6, 7]]，每个子数组表示二叉树中的一层节点的值。

小结

通过这次的题目，是不是让你对二叉树的遍历方式有了更加深刻的理解呢？如果递归遍历不是很熟悉的话，欢迎在我的《算法合集》中找到它并且阅读反思，如果你也和我一样，对算法有着浓厚的兴趣的话，欢迎订阅我的《算法合集》，我们一起战胜它！