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

题目链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/

本文基于JavaScript语言进行解题：一、广度优先、队列（每轮输出单个结点，为结点增加属性存放信息）　　二、广度优先、队列（每轮按层次输出）【巧妙】

应先了解：

一、广度优先、队列（每轮输出单个结点，为结点增加属性存放信息）

时间复杂度 O(N) ： N 为二叉树的节点数量，即 BFS 需循环 N 次。

 1 /**
 2  * @param {TreeNode} root
 3  * @return {number[][]}
 4  * 广度优先遍历、队列；
 5  * 进入队列之前，为每个结点增加一个用于记录深度的属性：depth；
 6  */
 7 var levelOrder = function (root) {
 8   if(root == null) return [];
 9   let result = [];
10   let queue = [];
11   root.depth = 0;
12   queue.push(root);
13   while(queue.length !== 0) {
14     let node = queue.shift();
15     // 为新的一层结点创建空数组容器。
16     if(result[node.depth] == null) result[node.depth] = [];
17     // 分层存储结点值
18     result[node.depth].push(node.val);
19     if(node.left != null) {
20       node.left.depth = node.depth + 1; // 比父结点更深一层
21       queue.push(node.left);
22     }
23     if(node.right != null) {
24       node.right.depth = node.depth + 1;
25       queue.push(node.right);
26     }
27   }
28   return result;
29 };

二、广度优先【队列】（每轮按层次输出）

相对第一种解法，这种更巧妙：在迭代的开始记录下队列的结点数（就是上一层结点数，因为这每轮迭代中都将上一层结点全部输出）。

时间复杂度 O(N) ： N 为二叉树的节点数量，即 BFS 需循环 N 次。

 1 /**
 2  * @param {TreeNode} root
 3  * @return {number[][]}
 4  */
 5 var levelOrder = function (root) {
 6   if (root == null) return [];
 7   let result = [];
 8   let queue = [];
 9   queue.push(root);
10   while (queue.length !== 0) {
11     let tmp = [];
12     // 巧妙的是这里：i的初始值记录了上一轮queue中的结点数，即使在本次迭代新增了结点也不会收到影响。
13     for (let i = queue.length; i > 0; i--) {
14       let node = queue.shift();
15       tmp.push(node.val);
16       if (node.left != null) queue.push(node.left);
17       if (node.right != null) queue.push(node.right);
18     }
19     result.push(tmp);
20   }
21   return result;
22 };