いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 429 N-ary tree inorder traversal

投稿日:

こんにちは

今回の学びは

recursiveでlevelをわたすことで従来のDFSでlevel orderを解くこともできる

 

 

問題はhttps://leetcode.com/problems/n-ary-tree-level-order-traversal/

前回の【アルゴリズム脳トレ】leetcode easy 589 N-ary tree preorder traversalがpreorderでしたが、inorderです。

かつ、アウトプットのフォーマットが違います!配列of 配列です。

関連記事は二分木の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:

    def levelOrder(self, root: 'Node') -> List[List[int]]:
        """
        if root is None: return [[]]
        stack = [root]
        ans = [root.val]
        while len(stack) > 0:
            # do making each layer as an array
            node = stack.pop()
            layer = [child.val for child in node.children]
            ans.append(layer)
        return ans
        """
        if root is None: return []
        stack = [root]
        ans = []  # [1, ]
        while len(stack) > 0:
            layer_ans = []
            layer_stack = []
            for node in stack:
                # do making each layer as an array
                layer_ans.append(node.val)
                if node.children is None: continue
                for child in node.children:
                    layer_stack.append( child )
            ans.append(layer_ans)
            stack = layer_stack
        return ans

 

 

「次のこの問題を解くばあい知っていればよい一つの事実とは?」

なし

 

 

別の回答で

recursiveでlevelをわたすことで従来のDFSでlevel orderを解くこともできる

https://leetcode.com/problems/n-ary-tree-level-order-traversal/discuss/341223/Python-DFS-solution

とうことを学びました。

iterativeしか頭になかったんですが、やっぱり皆様すごいですね。

 

まとめ

recursiveでlevelをわたすことで従来のDFSでlevel orderを解くこともできる

以上です

-アルゴリズム
-, ,

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