Problem :

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


My Solution :

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

from collections import deque


class Solution:
def connect(self, root: 'Node') -> 'Node':
queue = deque([(root, 0)])
while queue:
node, depth = queue.popleft()
if node:
if queue and (queue[0][1] == depth):
node.next = queue[0][0]
queue.append((node.left, depth+1))
queue.append((node.right, depth+1))
return root


Comment :

위 풀이는 내가 처음에 시도했던 것이다. 그런데 문제를 다시 읽어보니  "You may only use constant extra space." 라고 하네... 그래서 queue를 활용한 BFS가 아닌 다른 접근이 필요했다. 아래는 next를 먼저 지정하고 next를 따라 동일 level을 끝까지 순회하는 방법이다.


My Solution 2 :

class Solution:
def connect(self, root: 'Node') -> 'Node':
parent = root
while parent and parent.left:
curr = parent
while curr:
curr.left.next = curr.right
curr.right.next = curr.next and curr.next.left
curr = curr.next
parent = parent.left
return root


secret