从上往下打印二叉树

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

思路

使用宽度优先搜索层次遍历整个二叉树。
利用队列的FIFO的特性，把节点依次放进队列里。

代码

class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        if root is None:
            return [] #边界情况
        q = [root] #每次向队列中压住当前层次的节点
        result = [] #存放最终的结果
        while q:
            current_level = [] #记录当前层的节点的孩子
            for node in q:
                result.append(node.val)
                if node.left is not None:
                    current_level.append(node.left)
                if node.right is not None:
                    current_level.append(node.right)
            q = current_level
        return result