いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode easy 589 N-ary tree preorder traversal

投稿日:

こんにちは

今回の学びは

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はスタックを使って、うまく取り出すのよ。

以上です

-アルゴリズム
-, ,

Copyright© CTOの日記 , 2020 All Rights Reserved.