【アルゴリズム脳トレ】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を解くこともできる

以上です