[leetcode] PopulatingNextRightPointersinEachNode

package leetcode;

import leetcode.tag.NeedStudyMore;

@NeedStudyMore
/**
* <pre>
* 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
* </pre>
* */
public class PopulatingNextRightPointersinEachNode {

    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;
            connect(root.left);
            connect(root.right);
            connect(root.left, root.right);
        }

        public void connect(TreeLinkNode left, TreeLinkNode right) {
            while (left != null) {
                left.next = right;
                left = left.right;
                right = right.left;
            }
        }
    }
}