[LeetCode] 429 | N-ary Tree Level Order Traversal | Python

---

문제 링크: https://leetcode.com/problems/n-ary-tree-level-order-traversal/

---

문제

Given an n-ary tree, return the level order 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).

---

조건

• The height of the n-ary tree is less than or equal to 1000
• The total number of nodes is between [0, $10^4$]

---

내 풀이

Tree 관련 문제는 recursive하게 함수를 짠다.

함수에 입력으로 root와 함께 depth를 줘서 현재 노드의 depth가 몇인지 알 수 있게 한다.

현재 depth에 맞게 ans에 root.val을 추가하고, 현재 root의 children에 대해서 모두 search 함수를 적용한다.

---

코드

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

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        ans = []
        
        def search(root, depth):
            if not root:
                return
            
            if len(ans) < depth+1:
                ans.append([])
            
            ans[depth].append(root.val)
            
            for child in root.children:
                search(child, depth+1)
            
        search(root, 0)
        
        return ans