面试题32：从上到下打印二叉树

题目描述：

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

解题思路：

广度优先搜索，采用队列（按照层为单位，一层结束后出队列）
深度优先搜索，采用栈来实现

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        #广度优先搜素,以层为单位，一层结束后，就出队列。
        if root == None:
            return []
        quene = [root]
        res = []
        while quene:
            layer = quene
            quene = []
            for line in layer:
                res.append(line.val)
                if line.left:
                    quene.append(line.left)
                if line.right:
                    quene.append(line.right)
        return res