116. Populating Next Right Point

这里假定每棵树都是完美二叉树
思路:
首先验证是否存在当前节点,以及当前节点的左子节.
从当前层操作下一层,外层循环每次一都使层次下降一层,并使当前节点为当前层次最左端.
内层循环从最左端节点开始,用next每次循环向右移动一个节点,直到null.

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        while root and root.left:
            next = root.left
            while root:
                root.left.next = root.right
                root.right.next = root.next and root.next.left
                root = root.next
            root = next

注意,python中的and从左到右计算表达式，若所有值均为真，则返回最后一个值，若存在假，返回第一个假值。
or也是从左到右计算表达式，返回第一个为真的值,若都为假,返回最后一个假值.

117.假定给的树为任意二叉树
那么上面的策略就不能用了,因为不能保证最左端始终有节点.
这次的思路是:
引入两个节点prekid = kid = TreeLinkNode(0)
每层都开始于一个dummy node prekid
root在当前层,kid在下一层,
prekid.next是下一层的头结点
内层循环结束时,root, kid = prekid.next, prekid
把root变成下层的头结点,kid重新变为dummy node

def connect(self, root):
    prekid = kid = TreeLinkNode(0)
    while root:
        while root:
            kid.next = root.left
            kid = kid.next or kid
            kid.next = root.right
            kid = kid.next or kid
            root = root.next
        root, kid = prekid.next, prekid