[leetcode] Populating Next Right Pointers in Each Node

Problem Description:
Given a binary tree:

class 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.

• 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).  
• Follow up: What if the given tree could be any binary tree?

For example:

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

My first thought is using BFS to process the tree level by level. However, a regular BFS needs assistance of a queue, which is not constant space.
Anyway, the first problem (assuming a perfect binary tree) is relatively easy. By taking the similar strategy of solving Symmetric Tree problem, I got a very neat approach:

public class PopulatingNextRightPointersInEachNode {

    public void connect(TreeLinkNode root) {

        connect(root.left,root.right);

    }

    private void connect(TreeLinkNode n1,TreeLinkNode n2){

        if(n1==null||n2==null)

            return;

        n1.next=n2;

        connect(n1.left,n1.right);

        connect(n1.right,n2.left);

        connect(n2.left,n2.right);

    }

}

This approach is simple and neat, but has several drawbacks:

1. Not as efficient as optimal solution, as we can see in the following figure:

There are some repeated linking between node 7 and 8, 9 and 7. The result is correct, but when the tree size increases, this repeated linking cost may increase, too.
2. Definitely, this approach can't be applied to an arbitrary binary tree.

So, what can we do when it comes to any binary tree?

We can still try to process the tree level by level, but without a queue.
The trick part is that when we process the nodes of next level, we make sure that the current level has already been linked.
For example, when we deal with the third level, nodes 2 and 3 in level 2 have already been linked, then node5.next = node2.next.left( if not null), otherwise, keep searching towards right.

public class PopulatingNextRightPointersInEachNodeII {
    public void connect(TreeLinkNode root) {
        if(root==null)
            return;
        /**
         * current rightmost node
         */
        TreeLinkNode rightmost = null;
        /**
         * nextHead is the head node which is not null in next level
         *                1                   ----1
         *              /    \ 
         *             2     3               ----2
         *            / \    /   \
         *           6  7 8   9            ----3
         *              /    \     \
         *            10   11  12        ----4
         *            
         * e.g. node 10, it's the head of level 4 but not the left child of 6.
         */ 
        TreeLinkNode nextHead = null;
        TreeLinkNode temp = root;
        //connect next level of current root node level
        while(temp!=null){
            if(temp.left!=null)
                if(rightmost==null){
                    rightmost=temp.left;
                    nextHead=temp.left;
                }
                else{
                    rightmost.next = temp.left;
                    rightmost = rightmost.next;
                }
            if(temp.right!=null)
                if(rightmost==null){
                    rightmost=temp.right;
                    nextHead=temp.right;
                }
                else{
                    rightmost.next = temp.right;
                    rightmost = rightmost.next;
                }
            temp=temp.next;
        }
        //head in next level
        connect(nextHead);
    }
}