From 【左程云面试算法精品课】
二叉树层级遍历
class Node(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def create_tree():
t1 = Node(1)
t2 = Node(2)
t3 = Node(3)
t4 = Node(4)
t5 = Node(5)
t6 = Node(6)
t7 = Node(7)
t8 = Node(8)
t1.left = t2
t2.left = t4
t1.right = t3
t2.right = t5
t3.right = t6
t5.left = t7
t5.right = t8
return t1
如果层序遍历，直接用一个队列即可：
def printQ(root):
queue = []
lit = []
queue.append(root)
while queue:
out = queue.pop(0)
lit.append(out.val)
if out.left:
queue.append(out.left)
if out.right:
queue.append(out.right)
print " ".join(map(str, lit))
return
但是如果要去按层输出，每层一行，该怎么办？
用两个变量last和nlast分别记录当前行最右边的节点，和检测到的下一行的最右边的节点。
每次从二叉树拿出一个节点进入队列中，更新nlast为该节点。当这一层的节点都进入队列，就依次弹出节点打印，并判断弹出节点是否等于last。
当弹出节点 == last时，说明这一行已经打印完毕，令last=nlast,开始打印下一行。
def printS(root):
queue = []
last = root
nlast = root
queue.append(root)
lit = []
while queue:
out = queue.pop(0)
lit.append(out.val)
if out.left:
queue.append(out.left)
nlast = out.left
if out.right:
queue.append(out.right)
nlast = out.right
if out == last:
print " ".join(map(str, lit))
lit = []
last = nlast
return
s = create_tree()
printQ(s)
printS(s)
结果
1 2 3 4 5 6 7 8
1
2 3
4 5 6
7 8
