『剣指offer』【二叉木を複数行に印刷】(python版)


タイトルの説明:上から下へ二叉木を層別に印刷し、同じ層のノードを左から右に出力します.各層に1行出力します.
考え方:本題は実際には層序遍歴であるが、要点は同行しない結点をどのように分けるかである.ここで考慮するのは3つのリストを採用することである.Nodelistが前の行のノードのみを保存することを保証します.Nodelistのノードを巡り,左右の子供をcurnodelistに順次格納する.ループ終了curnodelistをnodelistに追加し、nodelistの最初の要素、すなわち前の行のノードを削除します.

class Solution:
    #       [[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        nodelist = []
        outlist = []
        if pRoot:
        # nodelist         ,                     
            nodelist.append([pRoot])
        else:
            return outlist
        while len(nodelist) and len(nodelist[0]):
            outlist.append([node.val for node in nodelist[0]])
            curnodelist = []
            #        ,       ,         
            for i in range(len(nodelist[0])):
                curnode = nodelist[0][i]
                if curnode.left:
                    curnodelist.append(curnode.left)
                if curnode.right:
                    curnodelist.append(curnode.right)
            #             
            nodelist.append(curnodelist)
            del nodelist[0]
        return outlist

ツリー構造のテスト:
![ツリー](ツリー)(https://img-blog.csdn.net/20180702175730219?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMTQxODY3/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)出力結果:
[[4], [2, 6], [3, 5, 7], [1]]