『剣指offer』【二叉木を複数行に印刷】(python版)
タイトルの説明:上から下へ二叉木を層別に印刷し、同じ層のノードを左から右に出力します.各層に1行出力します.
考え方:本題は実際には層序遍歴であるが、要点は同行しない結点をどのように分けるかである.ここで考慮するのは3つのリストを採用することである.Nodelistが前の行のノードのみを保存することを保証します.Nodelistのノードを巡り,左右の子供をcurnodelistに順次格納する.ループ終了curnodelistをnodelistに追加し、nodelistの最初の要素、すなわち前の行のノードを削除します.
ツリー構造のテスト:
![ツリー](ツリー)(https://img-blog.csdn.net/20180702175730219?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMTQxODY3/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)出力結果:
考え方:本題は実際には層序遍歴であるが、要点は同行しない結点をどのように分けるかである.ここで考慮するのは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]]