116. Populating Next Right Pointers in Each Node

Populating Next Right Pointers in Each Node - LeetCode

이진트리가 주어진다.

이진트리의 동일한 레벨을 왼쪽에서 오른쪽으로 연결하는 문제다.

 

1. BFS

from collections import deque, defaultdict


class Solution:
    def connect(self, root: 'Node') -> 'Node':
        q = deque([(root, 0)])
        dict1 = defaultdict(list)
        dict1[0].append(root)

        while q:
            cur_node, cur_level = q.popleft()
            if cur_node.left:
                dict1[cur_level + 1].append(cur_node.left)
                q.append((cur_node.left, cur_level + 1))
            if cur_node.right:
                dict1[cur_level + 1].append(cur_node.right)
                q.append((cur_node.right, cur_level + 1))

        for level in dict1:
            for i in range(len(dict1[level]) - 1):
                dict1[level][i].next = dict1[level][i + 1]
        return root

Dict에 동일 레벨의 노드를 append 한 뒤에 선형 탐색하면서 연결해줬다.

뭔가 더 멋진 방법이 있을 텐데 생각해내진 못해서 좀 더 고민해봐야겠다.