用一个队列实现按层遍历二叉树。遇到第1, 3, 7, 15, 31...个节点时(都和2的幂有关)让它们的next指向空, 判断N是不是1, 3, 7, 15, 31...的公式是 N & (N + 1) == 0, 位运算。

Use a queue to traverse the binary tree by level. When we meet the 1st, 3rd, 7th, 15th, 31th... node (note that they are close to 2^n), assign None to their "next" field. Bit operation can be used to check whether N is 1, 3, 7, 15, 31... or not. N & (N + 1) == 0

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None

class Solution:
    # @param root, a tree node
    # @return nothing
    def connect(self, root):
        if root == None: return
        visitedNum = 0
        queue = collections.deque()
        queue.append(root)
        while queue:
            curr = queue.popleft()
            visitedNum += 1
            if curr.left:
                queue.append(curr.left)
                queue.append(curr.right)
            curr.next = None if visitedNum & (visitedNum + 1) == 0 else queue[0]