#LeetCode# Populating Next Right Pointers in Each Node II

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

这个问题困扰了我快一个星期（小偷懒！）今天早晨拿出来重新看，仔细回味在某处看到的“先处理右子树”。有了灵光。

与上一个完全二叉树的问题比较，此树为任意树，意味着某个节点可能没有兄弟节点，或堂兄弟节点等，我们的难题在于怎么找到后继节点，怎么把当前节点与未知的XX节点链接起来。

所以，简化过程，

1. 先找到右孩子的第一个有效next链接节点

2. 左孩子nxet后继链接1中的有效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;

        }

    //1.先找右孩子第一个有效的next链接节点

    TreeLinkNode p = root.next;

    TreeLinkNode Node = null;

    while (p != null) {

        if (p.left != null) {

            Node = p.left;

            break;

        }

        if (p.right != null) {

            Node = p.right;

            break;

        }

        p = p.next;

    }

    

    //2. 左孩子nxet后继链接1中的有效next链接节点

    if (root.right != null) {

        root.right.next = Node;

    }

    

    if (root.left != null) {

        if (root.right != null) {

            root.left.next = root.right;

        } else {

            root.left.next = Node;

        }

    }

    

    //3.递归调用

    connect(root.right);

    connect(root.left);

    

    }

}

这里用Node来代表右孩子第一个有效的next链接节点，while语句判断两种情况，左子树不为空和左子树空右子树不为空。

接下来的链接过程与完全二叉树情况类同，不表。递归，注意先递归右子树，因为我们需要先处理右孩子/树。

好了，有点绕脑子的问题就停滞下来，该加把劲儿了。

LOL!