leetcode/python/ 589. N-ary Tree Preorder Traversal

Description

N-ary Tree Preorder Traversal - LeetCode

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 (See examples)

---

Process

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• 0 <= Node.val <= 104
• The height of the n-ary tree is less than or equal to 1000.

너 전위 순회 할 수 있니? 하고 묻는 문제다. 저는 이진트리로밖에 못해보긴 했는데요....... 설계 단계에서 조금 헤매긴 했는데 일단 root를 무조건 처음으로 넣는다부터 작성하고, 연결된 자식 노드들에 대해서 자식이 없을 때까지 재귀 호출하는 것으로 설계했다.

---

Solution

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        
        ans = [root.val]
        
        def traversal(root):
            if len(root.children) == 0:
                return
            for i in range(len(root.children)):
                ans.append(root.children[i].val)
                traversal(root.children[i])
            
        traversal(root)   
        return ans

 

1. not root 인 경우 예외처리

2. 정답 배열에 루트 in

3. traversal 함수로 children이 없을 때까지 재귀

 

 

---

Conclusion

어떻게 구현해야 할지는 조금 헤맸지만 설계한 대로 작성하니까 코드는 잘 돌아갔다. 물론 not root인 경우를 또 제출하고 잡긴 했다...... 이렇게 푸는 게 맞나 싶어서 다른 사람들 코드도 몇개 봤는데 비슷한 방식인 것 같다.