题解 | #从上往下打印二叉树#的Python解法

1. 解题思路

此题我们可以借助队列这个数据结构 + 层序遍历来解决。只要知道队列的特点是“先进先出”，那么此题就很好解决。

• 首先判断二叉树是否为空；
• 其次先把根节点放入队列，然后弹出根节点，添加到列表中；
• 开始遍历每一层，如果左右节点不为空，则放入队列里，接着弹出添加到列表；
• 重复前面的过程，直到二叉树节点为空。

2. 图解示例

输入：{5,4,#,3,#,2,#,1}
返回值：[5,4,3,2,1]

• 首先根据输入的二叉树数据，可以画出如下二叉树：
  

• 紧接着把根节点放入队列中这一步：
  

• 遍历每一层，左右节点是否为空；不为空就加入队列：
  

• 重复上面的过程，直到二叉树节点为空：
  

3. 核心代码

# -*- coding:utf-8 -*-
#class TreeNode:
#    def __init__(self, x):
#        self.val = x
#        self.left = None
#        self.right = None
class Solution:
    def PrintFromTopToBottom(self, root):
        # write code here
        if not root:           #首先判断是否存在root
            return []
        tree_node = []         #创建二叉树列表
        level = [root]         #每一层包含的节点
        while level:
            queue = level.pop(0)               #添加到辅助队列中
            tree_node.append(queue.val)        #弹出后添加到列表中
            if queue.left:                     #如果只存在左节点
                level.append(queue.left)
            if queue.right:                    #同理只存在右节点
                level.append(queue.right)

        return tree_node

4. 复杂度分析

• 时间复杂度：O(n) (与二叉树的节点个数有关）
• 空间复杂度：O(n) (就是最后得到的列表长度）

---------------------------------------------我是解法二的分割线----------------------------------------------

5.解法二：双端队列

5.1 思路

• 补充双端队列的知识点一：
  • 定义：
    
• 补充双端队列的知识点二：
  • 优势（或者为何用双端队列更优？）：
    因为列表要移除队首元素就只能把整个列表往前移动一位，这样它的复杂度就只能是O(n)；而双端队列不一样，它的底层其实是链表，所以队首插入或弹出都是O(1)的复杂度。
    
• 优化列表为deque双端队列，思路与解法一一致，不过主要用到其popleft()方法和append方法。
  

  5.2 核心代码

  # -*- coding:utf-8 -*-
  #class TreeNode:
  #    def __init__(self, x):
  #        self.val = x
  #        self.left = None
  #        self.right = None
  from collections import deque
  class Solution:
    def PrintFromTopToBottom(self, root):
        # write code here
        if not root:           #首先判断是否存在root
            return []
        tree_node, que = [], deque()    #初始化要打印二叉树的列表，以及双端队列对象
        que.append(root)
        while que:
            node = que.popleft()        #返回并弹出每层的队首元素
            tree_node.append(node.val)  #添加到二叉树打印列表中
            if node.left:               #只存在左节点的情况
                que.append(node.left)
            if node.right:              #只存在右节点的情况
                que.append(node.right)
        return tree_node

  5.3 复杂度分析

• 时间复杂度：O(1)（因为插入和弹出只需在两端进行）
• 空间复杂度：O(n) （与列表长度有关）