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

43日目に取り組んだ問題はこちら！
今日からまた、アルゴリズムの問題に戻ります。

589. N-ary Tree Preorder Traversal

問題文

Given the root of an n-ary tree, return the preorder 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

僕の回答

"""
# 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 preorder(self, root: 'Node') -> List[int]:
        stack = [root]
        result = []
        
        while stack:
            node = stack.pop()
            if not node:
                if not stack:
                    break
                else:
                    continue
            
            result.append(node.val)
            for child in node.children[::-1]:
                stack.append(child)
        
        return result

より効率の良い回答例

"""
# 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 preorder(self, root: 'Node') -> List[int]:
        if not root:  # rootがNoneの場合の早期リターン
            return []

        stack = [root]
        result = []
        
        while stack:
            node = stack.pop()
            if not node:
                continue
            
            result.append(node.val)
            if node.children:  # 子ノードがある場合のみ処理
                for child in node.children[::-1]:
                    stack.append(child)
        
        return result

学んだこと

• 以下の部分はcontinueで次のwhileで確認されるので不必要だった。

  if not stack:
      break
  

• 配列に後ろからアクセスする方法はarr[::-1]

コメント

今回の問題はすぐに思いついて、エラーなしで一回で成功したのでとても嬉しい！

次の問題はこちら!