LeetCodeを1日1題解いてみる (day44)

44日目に取り組んだ問題はこちら！

590. N-ary Tree Postorder Traversal

問題文

Given the root of an n-ary tree, return the postorder traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value

僕の回答 (GPTの助けあり)

"""
# Definition for a Node.
class Node:
    def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
        self.val = val
        self.children = children
"""

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        stack = [root]
        result = []
        
        while stack:
            node = stack.pop()
            if not node:
                if not stack:
                    break
                else:
                    continue
            
            for child in node.children:
                stack.append(child)

            result.append(node.val)
        return result[::-1]

他の回答例

"""
# Definition for a Node.
class Node:
    def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
        self.val = val
        self.children = children
"""

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        result = []

        def dfs(node):
            if not node:
                return
            for child in node.children:
                dfs(child)

            result.append(node.val)

        dfs(root)
        return result

学んだこと

Preorderとの違いは、

- for child in node.children[::-1]:
+ for child in node.children:

- return result
+ return result[::-1]

だけだということを学んだ。

コメント

以前にも似たような問題を解いたけど、忘れてしまっていたからしっかり理解して定着させたい。

次の問題はこちら!