57. Populating Next Right Pointers in Each Node II

/**
 * 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;
         root.next=null;
         dfs(root);
     }
   
     private void dfs(TreeLinkNode root){
         if(root==null) return;
         if(root.next==null){
             if(root.right!=null) root.right.next=null;
             if(root.left!=null) root.left.next=root.right;
         }else{
             TreeLinkNode p = root.next;
             TreeLinkNode q = null;
             while(p!=null){
                 if(p.left!=null) {q=p.left; break;}
                 if(p.right!=null) {q=p.right; break;}
                 p=p.next;
             }
             if(root.right!=null) root.right.next=q;
             if(root.left!=null&&root.right!=null) root.left.next=root.right;
             if(root.left!=null&&root.right==null) root.left.next=q;
         }
       
         dfs(root.right);
         dfs(root.left);
     }
}