-
429. N-ary Tree Level Order Traversal(Python, LeetCode Medium)LeetCode 2022. 9. 6. 03:21
문제 설명
트리의 각 레벨 요소끼리 묶어 리스트를 만들어 반환합니다.
입력
root: 'Node': 트리의 루트 정점
풀이
트리를 가로(레벨별)로 순회하는 문제입니다.
루트로부터 시작하여 각 레벨을 탐색하며 결과를 종합하므로, 시작 정점인 루트를 큐에 담는 것으로 동작을 시작합니다.
다음 레벨의 노드를 담을 큐를 생성하고, 현재 큐에 담긴 노드를 순회하며 자식 노드를 다음 레벨 큐에 저장합니다.
동시에 현재 큐에 담긴 노드의 val을 결과 배열에 삽입합니다.
현재 큐가 순회를 마치면 다음 큐의 순회를 시작하기 위해 현재 큐에 대입합니다.
만약 어떤 노드도 자식 노드를 갖고 있지 않아 다음 큐가 비게 된다면, 모든 노드를 탐색한 것이므로 결과를 반환합니다.
코드
더보기* Solution Class 이외 코드는 local test를 위한 코드입니다.
from collections import deque from typing import List, Optional 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]]: answer = [] if root is None: return answer queue = deque([root]) while queue: next_queue = deque() part = [] while queue: node = queue.popleft() part.append(node.val) for child in node.children: next_queue.append(child) answer.append(part) queue = next_queue return answer def make_tree(root: List[int]) -> Optional[Node]: root_node: Optional[Node] = None node: Optional[Node] = None queue = deque() for r in root: if root_node is None: root_node = Node(root[0], []) node = root_node queue.append(node) else: if r is None: node = queue.popleft() else: child_node = Node(r, []) node.children.append(child_node) queue.append(child_node) return root_node if __name__ == '__main__': solution = Solution() result = solution.levelOrder(make_tree(root=[1, None, 3, 2, 4, None, 5, 6])) print([[1], [3, 2, 4], [5, 6]] == result, result) result = solution.levelOrder(make_tree(root=[ 1, None, 2, 3, 4, 5, None, None, 6, 7, None, 8, None, 9, 10, None, None, 11, None, 12, None, 13, None, None, 14 ])) print([[1], [2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13], [14]] == result, result)
'LeetCode' 카테고리의 다른 글
(임시) 967. Numbers With Same Consecutive Differences(Python, LeetCode Medium) (0) 2022.09.08 (임시)94. Binary Tree Inorder Traversal(Python, LeetCode Easy) (0) 2022.09.08 606. Construct String from Binary Tree(Python, LeetCode Easy) (0) 2022.09.07 814. Binary Tree Pruning(Python, LeetCode Medium) (0) 2022.09.06 518. Coin Change 2(Python, LeetCode Medium) (0) 2022.09.04