问题描述：

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,

After calling your function, the tree should look like:

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

原问题链接：https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

问题分析

　　这个问题和前面的那个问题类似，因为不能借助任何其他的集合类的结构来帮助遍历树，而且树的结构也不像前面所描述的那样是一棵完美二叉树，那么这将意味着不是每个节点都包含有两个子节点的，有的可能有一个，也可能一个都没有。这个问题如果不结合一个具体的示例来推导的话，会显得非常的困难。

　　我们就以问题描述里的示例为基础，这个树的结构如下图：

　　我们最开始遍历的时候，肯定需要找到根节点。然后通过根节点去串联它下面的子节点。那么，当我们有一个引用指向根节点的时候，该怎么去串联它的子节点呢？因为它的子节点是不一定就存在的。而且，我们首先就需要找到它的那个存在的子节点才行，这样才能想办法将它所有可以访问到的子节点那一层都串起来。

　　有一个如下的办法可以解决，就是我们首先建立一个dummy节点，这个节点在某一层的节点遍历过程中指向它所有碰到过的非空节点，然后再根据循环中碰到的元素依次往前。这样相当于上面的节点遍历一遍之后也将它下面一层的节点给串起来了。详细的过程如下图：

　　首先我们建立了一个dummy节点，让它的next指向root节点。这样我们设置额外的两个节点分别为pre, n，它们的指向如下：

　　我们在设定了这个之后，再将当前节点的next引用设置为null。在我们从n开始往它的next去遍历时，我们在碰到非空的节点时，将pre的next节点和n的非空节点串起来。所以在上图中，当碰到节点2的时候，则情况如下：

　　因为前面将cur和pre设置为同一个引用，所以这一步就将它们的next引用指向了同一个节点。但在这一步找到一个节点之后，我们就将pre沿着next前进一步，如下图：

　　同样，如果我们碰到下一个非空的子节点呢，则继续将pre和前面串起来，如下图所示：

　　因此，上述过程可以概括成在n往next方向循环遍历的时候，判断它的左右子节点，如果有一个不为空，则pre.next = 这个不空的节点，然后再将pre = pre.next这样往前移。

　　这里还有一个问题就是，在一层遍历完之后，如果我们还需要去遍历下一层，就需要用到cur这个临时节点，我们需要将pre = cur，然后将cur.next赋值给n。然后再将cur, pre都设置为null。n再依次往next方向去遍历。这样直到我们的cur节点的next引用为空为止。所以上述过程中，cur节点起到一个记录点的作用，它的当前点作为下一个层次遍历的引用起始点，它的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) {
        TreeLinkNode nextHead = new TreeLinkNode(0);
        nextHead.next = root;
        while(nextHead.next != null) {
            TreeLinkNode tail = nextHead;
            TreeLinkNode n = nextHead.next;
            nextHead.next = null;
            for(; n != null; n = n.next) {
                if(n.left != null) {
                    tail.next = n.left;
                    tail = tail.next;
                }

                if(n.right != null) {
                    tail.next = n.right; 
                    tail = tail.next;
                }
            }
        }
    }
}