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分別記錄當(dāng)前行最右邊的節(jié)點，和檢測到的下一行的最右邊的節(jié)點。
每次從二叉樹拿出一個節(jié)點進(jìn)入隊列中，更新nlast為該節(jié)點。當(dāng)這一層的節(jié)點都進(jìn)入隊列，就依次彈出節(jié)點打印，并判斷彈出節(jié)點是否等于last。
當(dāng)彈出節(jié)點 == last時，說明這一行已經(jīng)打印完畢，令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)

結(jié)果

1 2 3 4 5 6 7 8
1
2 3
4 5 6
7 8