いいものをつくろう

CTOの日記

アルゴリズム

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

投稿日:

こんにちは

今回の学びは

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はスタックを使って、2回目にvisitしたときはとう判定変数を持たす。。複雑。

復習はこちら---> ( 二分木のpre-order, in-order, post-orderの簡単でわかりやすい説明  )

 

もっとうまく解いている人は?

https://leetcode.com/problems/n-ary-tree-postorder-traversal/discuss/440303/Python-3-Iterative-Faster-than-91.14-100-better-memorywiseさん、

え!?これで解けるの!?と疑いたくなるくらいシンプルです。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)にするだけ!と書いてあります。

https://leetcode.com/problems/n-ary-tree-preorder-traversal/discuss/460888/Simple-Iterative-Python-Solutiono

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

以上です

-アルゴリズム
-, ,

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