class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if not root: return
        cur = [root]
        next = []
        while len(cur) != 0:
            for i in range(len(cur)):
                if i != len(cur) - 1: cur[i].next = cur[i+1]
                if cur[i].left: next.append(cur[i].left)
                if cur[i].right: next.append(cur[i].right)
            if len(next) != 0:
                cur = next
                next = []
            else: return