Constant space and Linear time solution. 2ms Java


  • 0
    H
     public void connect(TreeLinkNode root) {
             TreeLinkNode start= root;
            while(start!=null){
                TreeLinkNode cur=searchNextNode(start);
                
                  while(cur!=null){
                        if(cur.left!=null && cur.right!=null)
                           {
                               cur.left.next=cur.right;
                           }
                        if(cur.right!=null && cur.next!=null){
                            TreeLinkNode next= searchNextNode(cur.next);
                            cur.right.next= (next==null)?null:((next.left!=null)? next.left:next.right);
                            cur=next;
                            continue;
                        }
                        if(cur.left!=null && cur.next!=null && cur.right==null){
                            TreeLinkNode next= searchNextNode(cur.next);
                            cur.left.next= (next==null)?null:((next.left!=null)? next.left:next.right);
                            cur=next;
                            continue;
                            
                        }
                        cur= searchNextNode(cur.next);
                  }
                  start=searchNextChildNode(start);
            }
        }
        public TreeLinkNode searchNextNode(TreeLinkNode node){
            if(node==null)
                return null;
            if(node.left!=null || node.right!=null)
                return node;
            return searchNextNode(node.next);
             
        }
        public TreeLinkNode searchNextChildNode(TreeLinkNode node){
            if(node==null)
                return null;
            if(node.left!=null)
                return node.left;
             if (node.right!=null)
                return node.right;
            return searchNextChildNode(node.next);
             
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.