리트코드 Populating Next Right Pointers in Each Node 코드 및 해설 (파이썬)

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

Populating Next Right Pointers in Each Node - LeetCode

 

BFS를 이용해 풀이했습니다. 먼저 root와 root의 depth인 1을 각각 다른 queue에 넣어주고 queue가 빌 때까지 다음을 반복합니다.

각 queue의 맨 첫번째 요소를 pop하고 이 요소의 depth와 남아있는 queue의 첫번째 요소의 depth가 같으면 next로 둘을 연결해줍니다. 그렇지 않으면 연결해주지 않고 default 상태로 NULL을 가리키도록 합니다. 이후 현재 노드의 left, right를 queue에 추가해주고, depth를 저장한 queue에도 현재 depth에서 1을 증가시킨 값을 추가해줍니다.

 

https://codlingual.tistory.com/182

DFS, 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: 'Node') -> 'Node':
        # queue with nodes
        queue = deque([root])
        # queue with depths
        depth = deque([1])
        
        while queue:
            node = queue.popleft()
            d = depth.popleft()
            
            # check if depth is same 
            if depth and depth[0] == d:
                node.next = queue[0]
            
            # prevent error when node in None 
            if node:
                children = [node.left, node.right]
                for child in children:
                    if child:
                        queue.append(child)
                        # increase depth by 1 
                        depth.append(d+1)
            
        return root