Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

You may only use constant extra space.
For example,
Given the following binary tree,

     1
   /  \
  2    3
 / \    \
4   5    7

After calling your function, the tree should look like:

    1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \    \
4-> 5 -> 7 -> NULL

这道题的关键点在于维系三个 变量：

• curt : the curt root we are passing as the method argument
• first : the first node in the level same as root's children'
• prev : the previous node we just connected to its next node in this level

每次循环要先确定first, 因为每次我们换行都会更新first为null, 所以要首先定下来新的first. 然后我们分别查看curt.left, curt.right, 如果左子树不为空，我们就要把之前刚连接好的node的next指向curt.left. 也就是prev.next = curt.left. 然而要这么做，我们必须先判断curt.left != null， 并且要注意prev == null 和prev != null两种情况。第一种情况说明这一层还没开始连next node, 那么直接设prev = curt.left就好了,；另一种情况就要连接之前连接的最后一个节点和目前的节点，即prev.next = curt.left. 右子树同理。最后连接完左右子树后，要确定curt所在level还有其他节点么,也就是curt.next == null? 如果没有了，则开始下一行的连接，更新curt, first, prev就可以了;如果还有，直接curt = curt.next 接着连接下一个。

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null){
            return;
        }
        TreeLinkNode curt = root;
        //the first node in the level where the children of root are
        TreeLinkNode first = null;
        //the last node finished connecting to its next in this level
        //(the same level as root's childreb).
        TreeLinkNode prev = null;
        while (curt != null){
            if (first == null){
                if (curt.left != null){
                    first = curt.left;
                } else if (curt.right != null){
                    first = curt.right;
                }
            }     
            if (curt.left != null){
                if (prev != null){
                    prev.next = curt.left;
                }
                prev = curt.left;
            }
            if (curt.right != null){
                if (prev != null){
                    prev.next = curt.right;
                }
                prev = curt.right;
            }
            if (curt.next != null){
                curt = curt.next;
            } else {
                curt  = first;
                prev = null;
                first = null;
            }
        }
    } 
}