剑指offer 面试题32 - I. 从上到下打印二叉树（中）

基于队列实现树的深度优先遍历即可。

Question

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

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

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7
返回： 
1
[3,9,20,15,7]
提示：节点总数 <= 1000

测试用例

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

本题考点

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

Intuition

思路很简单，基于队列实现树的深度优先遍历即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        if root == None:
            return []
        res = []
        queue = []
        queue.append(root)
        while len(queue):
            t = queue.pop(0)
            if t != None:
                res.append(t.val)
                queue.append(t.left)
                queue.append(t.right)
        return res

Extension

如何广度优先遍历一幅有向图？

同样也可以基于队列实现。树是图的一种特殊退化形式，从上到下按层遍历二叉树，从本质上来说就是广度优先遍历二叉树。

不管是广度优先遍历一幅有向图还是一棵树，都要用到队列。首先把起始节点（对树而言是根节点）放入队列。接下来每次从队列的头部取出一个节点，遍历这个节点之后把它能到达的节点（对树而言是子节点）都依次放入队列。重复这个遍历过程，直到队列中的节点全部被遍历为止。