[LeetCode][Python3] 116. Populating Next Right Pointers in Each Node

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