LeetCode 풀기 - 116. Populating Next Right Pointers in Each Node

116. Populating Next Right Pointers in Each Node

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

Populating Next Right Pointers in Each Node - LeetCode

문제)

솔루션1) - queue를 사용한 BFS

이진 트리 레벨 순회를 알고 있다면 살짝 응용해서 문제를 쉽게 풀 수 있습니다.

이진 트리 레벨을 이용하여 동일 레벨의 노드를 순회하면서 이전 노드의 정보를 가지고 있다가 next를 업데이트 수행하면 문제를 해결 할 수 있습니다.

"""
# 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':
        # BFS, Level order traversal
        # Queue 자료구조 사용
        # 동일 레벨에서 이전 노드 정보를 가지고 있으면서 next를 업데이트 수행

        q = deque()
        q.append(root)

        while q:
            prev_node = None
            for i in range(len(q)):
                current_node = q.popleft()
                if current_node:
                    if prev_node:
                        # 이전 노드의 next가 현재 노드를 가리키게 업데이트
                        prev_node.next = current_node

                    # 이전 노드를 업데이트
                    prev_node = current_node
                    
                    # 자식 노드를 queue에 추가
                    q.append(current_node.left)
                    q.append(current_node.right)

        return root

솔루션2) - Recursive

업데이트 예정!!!

 

 

함께 보면 좋은 글:

 

2021.11.20 - [알고리즘/알고리즘 Basic] - 이진 트리 레벨 순회 (Binary Tree Level Order Traversal)

이진 트리 레벨 순회 (Binary Tree Level Order Traversal)