LeetCode: 116. Populating Next Right Pointers in Each Node

O(N) 메모리를 사용한다면 매우 쉬운 문제이지만,

아래 Follow-up을 반영하여 O(1) 메모리를 사용하여 푸는 것은 조금 생각이 필요하다.

Constant Memory로 어찌 풀지 생각하다가 아래 조건에서 힌트를 얻었다.

Node의 개수에 제한이 있다는 것. Perfect Binary Tree에서 이와 같은 조건은 곧 최대 높이로 직결된다.

이를 활용하면, 트리의 층마다 last node 주소를 저장해놓고 갱신하는 방식으로 풀 수 있다.

"""
# 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: 'Node') -> 'Node':
        if not root:
            return
        self.node_address = [None] * 12
        self.dfs(root, 0)
        return root
        
    def dfs(self, node, height):
        if node == None:
            return
        if self.node_address[height] == None:
            self.node_address[height] = node
        else:
            self.node_address[height].next = node
            self.node_address[height] = node
        self.dfs(node.left, height+1)
        self.dfs(node.right, height+1)