Description
有一棵二叉树，请设计一个算法，按照层次打印这棵二叉树。
给定二叉树的根结点root，请返回打印结果，结果按照每一层一个数组进行储存，所有数组的顺序按照层数从上往下，且每一层的数组内元素按照从左往右排列。保证结点数小于等于500。
Solutions
1. Queue
但如果是要按照每层存为一个数组的方式打印（分层打印），上述的方式就没有办法实现了。难点在于如何知道换行，可以采用两个指针的方式来实现：
- last：表示正在打印的当前行的最右节点
- 当遍历到 last 结点说明要换行了
- 换行时需要将 last = next_last
- next_last：表示下一行的最右节点
- 一直跟踪 queue 新加入的结点即可，因为 queue 最新加入的结点一定是目前发现的下一层最右的节点
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class TreePrinter:
def printTree(self, root):
# write code here
if root is None:
return []
res = []
queue = [root]
level = []
last = next_last = root
while queue:
node = queue.pop()
level.append(node.val)
if node.left:
queue.insert(0, node.left)
next_last = node.left
if node.right:
queue.insert(0, node.right)
next_last = node.right
if node == last:
last = next_last
res.append(level)
level = []
return res
1.1 简单地自上而下打印
直接广度优先遍历，用 queue 实现既可：
# -*- 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 = []
queue = [root]
while queue:
node = queue.pop()
res.append(node.val)
if node.left:
queue.insert(0, node.left)
if node.right:
queue.insert(0, node.right)
return res
# 运行时间：34ms
# 占用内存：5856k