116. Populating Next Right Pointers in Each Node

这题不要想多了，如果在一层中间有 Null 的节点，那么此节点的 next 将指向下一个不是 Null 的节点。
方法一，用的是我最熟悉的 Level-Order-Traversal 的方法。
class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if not root:
            return
        q = collections.deque()
        q.append(root)
        q.append(None)
        while q:
            node = q.popleft()
            if node is None:
                if not q:
                    break
                q.append(None)
            else:
                node.next = q[0]
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)

#方法二，其实这道提示划归到了 DFS 的 topic 所以，这第二种方法，就是 DFS.
#在这个方法中，需要两个指针，pre指针每一个loop都指向每个level的最左边的值。然后用cur指针来把最左边的node的左右子树用next串起来cur.left.next = cur.right。
#如果，当前level还有右兄弟树，那么把当前node的右子树与右侧兄弟树的左子树串起来(cur.right.next = cur.next.left), 然后，cur = cur.next
class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if not root:
            return
        pre = root
        cur = None
        while pre.left:
            cur = pre
            while cur:
                cur.left.next = cur.right   #
                if cur.next:
                    cur.right.next = cur.next.left
                cur = cur.next

            pre = pre.left