"""
# 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
"""
# idea: use queue do level order traverse make sure current node's next can be pointed at neighbour node at the same level
class Solution:
def connect(self, root: 'Node') -> 'Node':
# space O(N) time O(N)
# step1: edge case: root is None
if not root:
return
# step2: initialize
q = collections.deque()
q.append(root)
# step3: set up traverse termination condition
while q:
# step 4.1: set limit each time only process one level
size = len(q)
for i in range(size):
node = q.popleft()
# step4.2 make sure current node is not right most node before connecting to left most of the queue
if q and i!= size-1 :
node.next = q[0]
# why or? since it's perfect binary tree so once child node exist, both left, right nodes exist
# step5: push children nodes into queue
if node.left or node.right:
q.append(node.left)
q.append(node.right)
return root
Iterative solution: main idea is to keep tracking parent node if it has next while reserve leftmost child 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':
# time O(N) space O(1)
# step1 cache return node
dummy = root
# step2: continue condition: root and root left node is not None
while root and root.left:
# step3 create parent pointer
cur = root
# step4 keep connecting left with right and prev right with current left
while cur:
cur.left.next = cur.right
cur.right.next = None if cur.next == None else cur.next.left
# parent pointer stop condition
cur = cur.next# reach all the way to end of level
# step5 parent node move to next level
root = root.left# next level start
return dummy
Recursive solution
"""
# 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 root
if root.left:
root.left.next = root.right
if root.right and root.next:
root.right.next =root.next.left
self.connect(root.left)
self.connect(root.right)
return root