From 【左程云面試算法精品課】
二叉樹(shù)層級(jí)遍歷
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
如果層序遍歷撕阎，直接用一個(gè)隊(duì)列即可：
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
但是如果要去按層輸出热押，每層一行，該怎么辦事扭？
用兩個(gè)變量last和nlast分別記錄當(dāng)前行最右邊的節(jié)點(diǎn)捎稚，和檢測(cè)到的下一行的最右邊的節(jié)點(diǎn)。
每次從二叉樹(shù)拿出一個(gè)節(jié)點(diǎn)進(jìn)入隊(duì)列中，更新nlast為該節(jié)點(diǎn)阳藻。當(dāng)這一層的節(jié)點(diǎn)都進(jìn)入隊(duì)列晰奖，就依次彈出節(jié)點(diǎn)打印谈撒，并判斷彈出節(jié)點(diǎn)是否等于last腥泥。
當(dāng)彈出節(jié)點(diǎn) == last時(shí)，說(shuō)明這一行已經(jīng)打印完畢啃匿，令last=nlast,開(kāi)始打印下一行蛔外。
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)
結(jié)果
1 2 3 4 5 6 7 8
1
2 3
4 5 6
7 8
