こんにちは
今回の学びは
・iterativeはスタックを使って、うまく取り出すのよ。
問題はn-ary-tree-postorder-traversal
前回の【アルゴリズム脳トレ】leetcode easy 589 N-ary tree preorder traversalがpreorderでしたが、postorderです。
preorderはrootがはじめにくるroot-first orderで
postorderとはrootが最後にくるroot-last orderです。木構造の操作の順番がちがうだけですが、
それぞれ用途があり頻繁にアルゴリズムに組み込まれるので名前がついています。
他にもinorder（私はroot-middle orderとよんでいます）くわしい説明はこちらの二分木のpre-order, in-order, post-orderの簡単でわかりやすい説明 記事にのっています。
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は
前回の【アルゴリズム脳トレ】leetcode easy 589 N-ary tree preorder traversalにつづき
post-orderの問題です。
実際の実装はこちら
class Solution_rec:
def __init__(self):
self.order = []
def postorder(self, root) -> List[int]:
"""
postっていうのは root-last order
なので
1
2 3
とうツリーの場合は2 -> 3 -> という順番でございます。
"""
def rec(root):
if root is None: return
for child in root.children:
rec(child)
self.order.append(root.val)
rec(root)
return self.order
フォローアップ問題は 前回のpre-orderの時も難しかったですが、今回も難しいあったです。
木の操作のstackバージョンはまだまだ不慣れです。。。
木構造の操作の基本が不安な方はこちらの記事が
二分木のpre-order, in-order, post-orderの簡単でわかりやすい説明 初心者向けで最初に読むといい思います。
from collections import namedtuple
Track = namedtuple('Track', ['node', 'visisted'])
class Solution:
def postorder(self, root) -> List[int]:
if root is None: return []
stack, order = [Track(root, 1)], []
curr = root
while curr or len(stack) > 0:
if curr:
if curr.children and len(curr.children) > 0:
for i in range(len(curr.children)-1, -1, -1):
node = curr.children[i]
if i == 0:
stack.append(Track(node, 1))
else:
stack.append(Track(node, 0))
curr = curr.children[0]
else:
curr = None
else:
track = stack.pop()
curr, visited = track.node, track.visisted
if curr.children is None or len(curr.children) == 0 or visited == 1:
order.append(curr.val)
curr = None
else:
stack.append(Track(curr, 1))
return order
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
iterativeはスタックを使って、２回目にvisitしたときはとう判定変数を持たす。。複雑。
復習はこちら---> ( 二分木のpre-order, in-order, post-orderの簡単でわかりやすい説明 )
もっとうまく解いている人は？
え！？これで解けるの！？と疑いたくなるくらいシンプルです。if node.childrenはNoneになりうるのでそこのvalidationをしただけで
見事に動作します。
class Solution_lc:
def postorder(self, root: 'Node') -> List[int]:
if not root:
return []
stack = [root]
self.list = []
while stack:
node = stack.pop()
self.list.append(node.val)
if node.children:
for i in node.children:
stack.append(i)
print(self.list)
return self.list[::-1]
似たような回答として、回答はpreorderなのですが、postorderはpop(0)にするだけ！と書いてあります。
Build a stack, and put children into the stack, this is the same a postorder, just replace the pop() by pop.(0)
class Solution:
def preorder(self, root: 'Node') -> List[int]:
if not root:
return []
stack = [root]
res = []
while len(stack) > 0:
current = stack.pop()
res.append(current.val)
if current.children:
for node in current.children[::-1]:
stack.append(node)
return res
above code is from https://leetcode.com/problems/n-ary-tree-preorder-traversal/discuss/460888/Simple-Iterative-Python-Solutiono
iterativeでの実装方法は何回も見返す可能性があるので
preorder, postorder, levelorderをiterativeに実装する の別ページでもまとめています。
まとめ
・iterativeはスタックを使って、うまく取り出すのよ。
以上です