Populating Next Right Pointers in Each Node

这两道题有一个关键的地方需要想通，首先我们可以假设第i层我们已经连接好了，那我们应该如何连接第i+1层？显然办法就是横向利用next指针把所有结点的孩子连接起来，而因为next指针的存在，我们就可以不需要队列来实现BFS了

# Definition for binary tree with next pointer.
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if not root:
            return 

        while root.left:
            cur = root
            while cur:
                cur.left.next = cur.right
                if cur.next:
                    cur.right.next = cur.next.left
                cur = cur.next
            root = root.left

Populating Next Right Pointers in Each Node II

这道题我们需要考虑非perfect tree的情况，逻辑判断复杂很多，且需要一个pre变量来记住上一个连接过的结点，因为这里的每个结点不一定都有左右孩子，另外我们需要一个额外的while循环把同层一开始所有没有左右孩子的点跳过，还需要一个nextRoot变量来记录头一个有孩子的结点，因为我们下一层的起点就是这里

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

            nxtRoot = cur.left if cur.left else cur.right
            while cur:
                if pre:
                    pre.next = cur.left if cur.left else cur.right

                if cur.left and cur.right:
                    cur.left.next = cur.right
                    pre = cur.right
                elif cur.left and not cur.right:
                    pre = cur.left
                elif cur.right and not cur.left:
                    pre = cur.right

                cur = cur.next

            root = nxtRoot