Populating Next Right Pointers in Each Node II

package Level4;  
  
import Utility.TreeLinkNode;  
  
/** 
 * 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 
Discuss 


 * 
 */  
public class S117 {  
  
    public static void main(String[] args) {  
  
    }  
  
    public static void connect(TreeLinkNode root) {  
        // 空节点就直接返回  
        if (root == null){  
            return;  
        }  
          
        // 找到与root同一行的next node  
        TreeLinkNode rootNext = root.next;  
        TreeLinkNode next = null;       // 下一个被连接的对象  
          
        // rootNext如果是null说明已经处理完这一层的所有node  
        // next不等于null说明找到了找到最左边的下一个被连接的对象  
        while (rootNext != null && next == null)  
        {  
            if (rootNext.left != null){ // 优先找左边  
                next = rootNext.left;  
            } else{  
                next = rootNext.right;  
            }  
            rootNext = rootNext.next;  
        }  
   
        if (root.left != null)  
        {  
            if (root.right != null){    //  内部相连  
                root.left.next = root.right;  
            }else{                      // 跨树相连  
                root.left.next = next;  
            }  
        }  
        if (root.right != null){        // 跨树相连  
            root.right.next = next;  
        }  
          
        connect(root.right);        // 要先让右边都先连起来  
        connect(root.left);  
    }  
}