116. Populating Next Right Pointers in Each Node (Linked List, Tree, Depth-First Search, Breadth-First Search, Binary Tree)

링크 - https://leetcode.com/problems/populating-next-right-pointers-in-each-node/description/?envType=company&envId=facebook&favoriteSlug=facebook-three-months

난이도 - Medium

Intuition

1) BFS

이 문제는 BFS를 통해 풀 수 있다. 우리는 이 Tree가 Perfect binary Tree임을 알고 있으므로, 매번 1, 2, 4, 8,..개의 노드들을 처리해야한다는 것을 알 고 있다. 따라서 이 값을 추적하면서 BFS를 하면 쉽게 문제를 풀 수 있다.

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return root

        queue = deque()
        queue.append(root)

        num_nodes_to_count = 1
        cur_count = 0
        prev = None
        while queue:
            node = queue.popleft()
            cur_count += 1

            if prev is not None:
                prev.next = node
            prev = node

            if cur_count == num_nodes_to_count:
                cur_count = 0
                num_nodes_to_count *= 2
                prev = None

            if node.left and node.right:
                queue.append(node.left)
                queue.append(node.right)

        return root

Time Complexity: O(N) 우리는 한번에 하나의 노드씩 모든 노드를 탐색하므로 O(N)이다. 

Space Complexity: O(N) BFS를 통해 문제를 푸므로, 마지막 level에서의 노드의 개수는 N/2개이다. 따라서 최대 N/2개의 노드들이 deque에 담길 것이므로, O(N)이다.

2) Using previously established next pointers (O(1) space complexity)

우리는 각 level에서 아래 level에 대해 작업을 수행할 수 있다. 우리가 살펴야 할 것은 두가지 케이스이다.

 

위의 이미지는 자식 노드들을 어떻게 이어주는지를 보여준다. 예를 들어, 1의 자식노드 2와3을 연결하기 위해서는, 

node.left.next = node.right을 해줘야 한다.

하지만 자식노드들의 자식노드들을 이어주다보면 문제가 생긴다. 5와6같이 같은 부모가 아닌 노드들도 연결해줘야 하기 때문이다. 이같은 경우에는 다음 코드로 이어준다.

node.right.next = node.next.left

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return root

        # Start with the root node. There are no next pointers
        # that need to be set up on the first level
        leftmost = root

        # Once we reach the final level, we are done
        while leftmost.left:

            # Iterate the "linked list" starting from the head
            # node and using the next pointers, establish the
            # corresponding links for the next level
            head = leftmost
            while head:
                # CONNECTION 1
                head.left.next = head.right
                # CONNECTION 2
                if head.next:
                    head.right.next = head.next.left
                
                # Progress along the list (nodes on the current level)
                head = head.next

            # Move onto the next level
            leftmost = leftmost.left

        return root

Time Complexity: O(N) 모든 노드들(N)을 방문하기 때문이다.

Space Complexity: O(1)