The main idea is to use a generator function
childrenGen to generate all nodes for the current level, one by one, from left to right. Every time a new node is generated, we connect the current node to the new node, and call the new node current, until the current level is done. Then we use the leftmost node to seed the generator for the next level. Using generating function guarantees O(1) space at the same time simplifies the logic.
class Solution: # @param root, a tree node # @return nothing def connect(self, root): genChild = self.childrenGen(root) # the generator seeded by the leftmost node of the parent level first = genChild.next() # the leftmost node at the current level while first: node = first while node: node.next = node = genChild.next() genChild = self.childrenGen(first) first = genChild.next() def childrenGen(self, p): while p: if p.left: yield p.left if p.right: yield p.right p = p.next yield None return