# Just convert common BFS solution to O(1) space, a simple python code

• common BFS

``````class Solution:
# @param root, a tree link node
# @return nothing
def connect(self, root):
if not root:
return
queue, level = collections.deque([root]), collections.deque()
while queue:
node = queue.popleft()
if node.left:
level.append(node.left)
if node.right:
level.append(node.right)
node.next = queue[0] if queue else None
if not queue and level:
queue, level = level, queue
``````

O(1) space

``````class Solution:
# @param root, a tree link node
# @return nothing
def connect(self, root):
queue, level, curr = root, None, None
while queue:
if queue.left:
if not level:
level = curr = queue.left
else:
curr.next = queue.left
curr = curr.next
if queue.right:
if not level:
level = curr = queue.right
else:
curr.next = queue.right
curr = curr.next
queue = queue.next
if not queue and level:
queue, level, curr = level, None, None
``````

Use a fake head can save a few lines

• Good answer, while the first BFS case can also be written as:

``````# BFS with queue
def connect(self, root):
if not root:
return
queue, nextLevel = [root], []   # queue records the previous level
while queue:
curr = queue.pop(0)
if curr.left:
nextLevel.append(curr.left)
if curr.right:
nextLevel.append(curr.right)
if queue:
curr.next = queue[0]
if not queue and nextLevel:
queue, nextLevel = nextLevel, queue``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.