117. Populating Next Right Pointers in Each Node II

这道题与 116 类似。同样是两种方法。
方法一： 依旧是我最熟悉的方法 level-order-traversal 但是好像同样是用level-order好像还有一个比我写的更加简洁的。
ps. 这道题是第二遍做了，这一遍写的方法，没有第一边做这道题写的方法好。感觉原因出在总是考虑 internal node 的左或右子树为 Null 的情况。其实level-order 不用考虑这种情况。比如, [1,2,3,4,null,null,5] --level.--> [[1],[2,3],[4,5]] 中间的null是自动去除的。所以直接写成如下结果便好。
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:
            if q[0] is None:
                q.popleft()
                if not q:
                    break
                q.append(None)
            else:
                q[0].next = q[1]
                if q[0].left:
                    q.append(q[0].left)
                if q[0].right:
                    q.append(q[0].right)
                q.popleft()