[python3] 429. N-ary Tree Level Order Traversal

풀이 일자: 22.09.05

난이도: [Medium]

분류: [BFS/ Tree]

문제 내용

주어진 n-ary tree를 가지고 각 level의 노드값들의 리스트들을 하나로 묶어서 리턴하는 문제이다.

 

문제 해결 흐름

1. 문제에서 level별 순회값을 리턴하라고 어떻게 풀어야 하는지 제시해주었다.

→ 대놓고 BFS쓰라는 거구나. 그래도 일단 익숙한 DFS로 풀어보았다.

"""
# 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 = list()
        
        dq = deque()
        dq.append((root,0))
        
        while dq:
            node, level = dq.popleft()
            if node:
                if len(ans) <= level:
                    ans.append([])
                ans[level].append(node.val)
                for child in node.children:
                    dq.append((child, level + 1))
        
        return ans

 

2. 문제에서 요청한 대로 BFS로 풀어본다면...

 

 

다른 해결 방식

 

문제 링크

https://leetcode.com/problems/n-ary-tree-level-order-traversal/