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