In each iteration of BFS we can process the entire level, linking the nodes with next pointer.
Time: 
"""
# 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: 'Optional[Node]') -> 'Optional[Node]':
if not root:
return None
q = deque([root])
while q:
level_len = len(q)
for i in range(level_len):
u = q.popleft()
u.next = q[0] if i < level_len-1 else None
q.extend(c for c in (u.left, u.right) if c)
return root
Follow-up: Use only constant extra space.
Since the implicit stack of recursion is not counted as extra space, we can connect siblings. The right child should point to the left cousin.
"""
# 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: 'Optional[Node]') -> 'Optional[Node]':
def connect_sibling(root) -> None:
if not root or (not root.left and not root.right):
return
root.left.next = root.right
root.right.next = root.next.left if root.next else None
connect_sibling(root.left)
connect_sibling(root.right)
connect_sibling(root)
return root
unreasonably effective 
Leave a comment