#LeetCode# Populating Next Right Pointers in Each Node

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

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

题目有点长，populate是填入、构成的意思。题目大意是，对每一个节点用指针后继与其右边节点链接起来，如果节点右边没有节点，则指针后继为Null。题目假设给定的树为完全二叉树，给定常数额外空间。

可笑的喔，上来先看图，把题目理解成广度优先搜索挨个把节点值置换为Null，真是可笑。

思路马上就有了，对节点进行链表处理，left.next = right，这样的处理比单双向链表的删除插入还要简单。不过我们还是不能大意，

1.对于，题图中的2、3节点，由于是同一个节点的左右孩子节点，root.left.next = root.right即可

2.对于题目中5、6节点呢？5和6节点不在同一个节点上。我们用root2和root3分别表示2、3节点，root2.left.next = root3.left可以处理。可是，root2和root3该如何表示呢？不要忘了，在上一层，这个时候的3节点已经是2节点的后继节点了，所以我们有root2.right.next = root.next.left。

具体处理的逻辑已经确定，我们下一步需要确定的是条件语句，核心判断节点是否为Null。直接上代码，

/**

 * 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;

        if (root.left != null) {  //父节点非空的情况，如2和3

            root.left.next = root.right;

        }

        if (root.right != null && root.next != null) { //不是兄弟节点的情况，如5和6

            root.right.next = root.next.left;

        }

        

        connect(root.left);

        connect(root.right);

        

    }

}

OK！洗漱滚上床去。