こんにちは
今回の学びは
・iterativeはスタックを使って、うまく取り出すのよ。
問題はn-ary-tree-preorder-traversal
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は
問題の理解がしにくいと感じましたが、pre-orderの問題です。
実際の実装はこちら
class Solution_rec:
def __init__(self):
self.order = []
def rec(self, root) -> List[int]:
if root is None: return
self.order.append(root.val)
for child_node in root.children:
self.preorder(child_node)
def preorder(self, root) -> List[int]:
self.rec(root)
return self.order
フォローアップ問題は難しかったです
まずは簡単な木の操作の復習が必要でした。こちらでやりました。
二分木のpre-order, in-order, post-orderの簡単でわかりやすい説明
その後とけました。
class Solution:
def preorder(self, root) -> List[int]:
stack, order = [], []
curr = root
i = 0
while curr or len(stack) > 0:
i = 0
if curr: #ポインタがあるとき
# do something
order.append(curr.val)
stack.append((curr, i)) # 現在ノードiは終わったよ（終わるつもり）。次はi+1してね。という意味
if len(curr.children) > i:
curr = curr.children[i] # 左にすすめ
else:
curr = None
i = 0
else: #stackがあるので
curr, i = stack.pop()
i = i + 1 # I want do next one!
# do something
#curr = curr.right # 右にすすめ
if len(curr.children) > i:
stack.append((curr, i))
curr = curr.children[i] # 左にすすめ
else:
curr = None
i = 0
return order
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
iterativeはスタックを使って、うまく取り出すのよ。
復習はこちら---> ( 二分木のpre-order, in-order, post-orderの簡単でわかりやすい説明 )
まとめ
・iterativeはスタックを使って、うまく取り出すのよ。
以上です