剑指offer 面试题32 - II. 从上到下打印二叉树 II（易） & LeetCode 102. 二叉树的层序遍历（中）

在剑指offer 面试题32 - I. 从上到下打印二叉树（中）的基础上略作修改即可。

Question

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

例如：给定二叉树: [3,9,20,null,null,15,7], 

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7
返回其层次遍历结果： 
1
2
3
4
5
[
  [3],
  [9,20],
  [15,7]
]
提示：节点总数 <= 1000

Intuition

用一个队列来保存将要打印的节点。为了把二叉树的每一行单独打印到一行里，我们需要两个变量：一个变量表示在当前层中还没有打印的节点数；另一个变量表示下一层节点的数目。

测试用例

功能测试（完全二叉树；所有节点只有左子树的二叉树；所有节点只有右子树的二叉树）。 特殊输入测试（二叉树根节点为nullptr指针；只有一个节点的二叉树）。

本题考点

考查应聘者的思维能力。按层从上到下遍历二叉树，这对很多应聘者来说是一个新概念，要在短时间内想明白遍历的过程不是一件容易的事情。应聘者通过具体的例子找出其中的规律并想到基于队列的算法，是解决这个问题的关键。

考查应聘者对二叉树及队列的理解。

Code

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
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if root == None:
            return []
        res = []
        queue = []
        queue.append(root)
        count = 0  # 另一个变量表示下一层节点的数目。
        to_be_printed = 1  # 一个变量表示在当前层中还没有打印的节点数；
        tmp = []
        while len(queue):
            t = queue.pop(0)
            if t != None:
                tmp.append(t.val)
                to_be_printed -= 1
                if t.left:
                    queue.append(t.left)
                    count += 1
                if t.right:
                    queue.append(t.right)
                    count += 1
            if to_be_printed == 0:
                to_be_printed = count  # 用count更新to_be_printed
                count = 0
                res.append(tmp[:])
                tmp = []
        return res