Day3-从上到下打印二叉树_第3关:打印二叉树

题目描述

剑指offer 32 从上到下打印二叉树

1. 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
2. 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
3. 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

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

 	3
   / \
  9  20
    /  \
   15   7
1
2
3
4
5

1、2、3的结果分别如下：

1.
	[3,9,20,15,7]
2.
    [
      [3],
      [9,20],
      [15,7]
    ]
3.
	[
      [3],
      [20,9],
      [15,7]
	]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

第一问

解题思路

按层打印二叉树，即二叉树的广度优先搜索（BFS），通常我们可以利用队列的先进先出特点来进行层序遍历，每次从队首弹出一个节点node，并判断这个节点有没有左右子节点，有的话就分别添加到队尾，然后把这个节点node加入到结果队列中，循环执行以上操作即可,当队列为空时退出循环。

这里使用python进行解题，可以使用collections中的双端队列deque，其从队首弹出的函数 popleft()的时间复杂度为O(1)

复杂度

时间复杂度：O(n)，遍历n个节点

空间复杂度： O(n),用到了双端队列n的额外空间

补充

双端队列的初始化： queue = collections.dequeue(,[[ ])括号里是可选参数，默认空列表，参数可以是一个列表，即把列表转化为双端队列。

一些方法：

queue.pop()

queue.popleft()

queue.append(value)

queue.appendleft(value)

代码实现

# 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 not root: return []
        res , queue = [] , collections.deque([root])
        while queue:
            node = queue.popleft()
            res.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        return res
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

第二问

解题思路

第二问要求同一层的节点要打印在一行，因此我们可以额外增加一个列表tmp用来存储同一层的节点值。

算法流程

1. 特例处理：若树为空，返回空列表
2. 初始化：用一个列表res存储最终结果，双端队列queue初始化存入根节点root
3. BFS循环：当队列queue为空时退出：
   1. 新建tmp空列表，用于存储同一层的节点值
   2. 循环按层打印，循环次数为当层节点数，即queue的长度：
      1. 出队：queue中的第一个节点赋值给node
      2. 添加到tmp：将node.val添加到列表里
      3. 入队：若有子节点，则入入队
   3. 将当前层的结果tmp添加到res
4. 返回结果res

复杂度

时间复杂度：O(n), 遍历n个节点

空间复杂度：O(n),最差的情况下，当树为平衡二叉树时，最多有N/2个节点在队列queue中，用到O(n)的额外空间。

代码实现

# 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[List[int]]:
        if not root: return []
        res , queue = [] , collections.deque([root])
        while queue:
            tmp = []
            for _ in range(len(queue)):				#循环次数为当层节点数
                node = queue.popleft()
                tmp.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            res.append(tmp)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

第三问

解题思路

第三问在第二题的基础上增加要求：即以之字形打印，可以看到奇数层从左往右打印，偶数层从右往左打印，因此可以通过一个标识符来判断奇偶层并执行对应的操作：

偶数层从队尾出队，左、右子结点从队首入队，以此达到反转打印的效果。

奇数层从队首出队，**左、右**子结点从队尾入队；

但是这样子奇数层顺序和预期相反，因此我们可以交换左右子节点入队的顺序，即右结点先入队，左结点后入队。

复杂度

时间复杂度：O(n) , BFS循环n次，n为节点数。

空间复杂度：O(n) , 同第二问。

代码实现

# 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[List[int]]:
    	if not root: return []
        res , queue = [] , collections.deque([root])
        flag = True  			#奇偶标识
        while queue:
            tmp = []
            for _ in range(len(queue)):
                if flag: 
                    node = queue.popleft()
                    tmp.append(node.val)
                    if node.left: queue.append(node.left)
                    if node.right: queue.append(node.right)
               else:
                    node = queue.pop()
                    tmp.append(node.val)
                    if node.right: queue.appendleft(node.right)
                    if node.left: queue.appendleft(node.left)           
            res.append(tmp)
            flag = not flag
      return res
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

欢迎访问我的博客：[Victor's Blog](http://www.victorcoding.top)