面试题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 is None:
            return []  #如果为空，直接返回空列表
        #保存节点的缓存队列
        res = []
        res_val = []
        res.append(root)
        while len(res)>0:
            Node = res.pop(0)        #将队列头部的节点取出
            res_val.append(Node.val)#加入打印的列表的尾端
            if Node.left:            #如果该节点有左节点将其加入队列尾端
                res.append(Node.left)
            if Node.right:           #如果该节点有右节点将其加入队列尾端
                res.append(Node.right)
        return res_val              #最终返回值列表

提交结果：

————————————————————————————————
题目二：
分行打印按照层次遍历的结果

解题思路：
这道题和上一题目思路一样，但是多了一个换行控制，将同一层的val添加到一个列表，当需要换行时把这一列表的值全部添加到打印列表，然后进行下一层的列表添加。为此需要引入两个变量，一个是当前层需要打印的节点数，一个是下一层的总节点数，当当前层次需要打印的节点数为0是进行当前层的列表添加操作并且进行变量更新以便于下层的打印。

代码实现：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def Print(self, pRoot):
        # write code here
        if pRoot ==  None:
            return []
        res = []
        res_val = []
        res.append(pRoot)

        ToBePrint = 1 #根节点为一个节点
        NextLevel = 0 #下一层的节点数
        temp = []     #储存每层节点的变量 
        while len(res)>0:
            
            node = res.pop(0)
            temp.append(node.val)
            ToBePrint -=1    #要打印的数目减1

            if node.left:
                res.append(node.left)
                NextLevel+=1  #x下一层节点数加1
            if node.right:
                res.append(node.right)
                NextLevel+=1
            if ToBePrint ==0: #该层的节点数已经打印结束
                res_val.append(temp)
                
                ToBePrint = NextLevel  #更新变量
                NextLevel = 0
                temp = []
        return res_val

提交结果：

—————————————————————————————————
题目三：
之字型打印二叉树

思路：
这道题可以受上面题目二的启发，即在上述的条件下，再增加一个lefttoright的变量，初始化为true，一层打印结束之后，将lefttoright反转，当lefttoright到为真时，和上述一致，当为假时，将temp倒叙加入到列表中，具体如下：

32 之字形打印二叉树.png

代码实现：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def Print(self, pRoot):
        # write code here
        if pRoot ==  None:
            return []
        res = []
        res_val = []
        res.append(pRoot)
        leftToright = True

        ToBePrint = 1 #根节点为一个节点
        NextLevel = 0 #下一层的节点数
        temp = []     #储存每层节点的变量 
        while len(res)>0:
            
            node = res.pop(0)
            temp.append(node.val)
            ToBePrint -=1    #要打印的数目减1

            if node.left:
                res.append(node.left)
                NextLevel+=1  #x下一层节点数加1
            if node.right:
                res.append(node.right)
                NextLevel+=1
            if ToBePrint ==0: #该层的节点数已经打印结束
                if leftToright:
                    res_val.append(temp)
                else:
                    res_val.append(temp[::-1])
                ToBePrint = NextLevel  #更新变量
                NextLevel = 0
                temp = []
                leftToright = not leftToright
        return res_val

提交结果：