剑指 Offer 32 - II. 从上到下打印二叉树 II

题目描述：

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

示例：

给定二叉树: [3,9,20,null,null,15,7],
在这里插入图片描述

返回结果为：
在这里插入图片描述

思路：

从题目中可以看到，本题考察的是二叉树的层序遍历，并且在结果中要体现出“层次”。
稍微改变一下对队列的使用，就可以在遍历过程中体现出层次，大致过程如下：

  1. 初始化 queue，用于存储当前层的节点
  2. 检查 queue 是否为空
     2.1:如果不为空：依次遍历当前 queue 内的所有节点，检查每个节点的左右子节点，将不为空的子节点放入 queue，继续循环  
 2.2:如果为空：跳出循环

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
var levelOrder = function(root) {
  if (!root) return [];
  // 1. 设置结果集
  const result = [];
  // 2. 设置当前层
  let nowRoot = [root];
  // 3. 广度优先搜索（BFS）
  while (nowRoot.length) {
    // 3.1 设置下一层
    const nextRoot = [];
    // 3.2 设置当前层的值
    const nowResult = [];
    // 3.3 遍历当前层，取值以及添加下一层
    for (let i = 0; i < nowRoot.length; i++) {
      // 3.3.1 添加值
      nowResult.push(nowRoot[i].val);

      // 3.3.2 如果存在左子树
      if (nowRoot[i].left) {
        nextRoot.push(nowRoot[i].left);
      }
      // 3.3.3 如果存在右子树
      if (nowRoot[i].right) {
        nextRoot.push(nowRoot[i].right);
      }
    }
    // 3.4 收集完毕，开始交接
    nowRoot = nextRoot;
    result.push(nowResult);
  }
  // 4. 返回结果
  return result;
}