Easy and short python solution using O(1) space


#1
def connect(self, root):
    s_up = root
    while s_up is not None:
        i_up = s_up
        dummy = TreeLinkNode(0)
        i_dn = dummy
        while i_up is not None:
            if i_up.left is not None:
                i_dn.next = i_up.left
                i_dn = i_dn.next
            if i_up.right is not None:
                i_dn.next = i_up.right
                i_dn = i_dn.next

            i_up = i_up.next
        i_dn.next = None
        s_up = dummy.next
        del dummy
    return root