Java straight forward O(1) space and O(n) time solution


  • 0
    X
    public void connect(TreeLinkNode root) {
        TreeLinkNode curhead = root;
        TreeLinkNode prehead = root;
        TreeLinkNode cur = curhead;
        TreeLinkNode pre = prehead;
        while(curhead!=null){
            pre = prehead;
            //Find the head of next line
            while(pre!=null&&pre.left==null&&pre.right==null){  
                pre = pre.next;
            }
            if(pre == null){
                break;
            }else if(pre.left!=null){
                curhead=pre.left;
                cur=curhead;
                if(pre.right!=null){
                    cur.next=pre.right;
                    cur = cur.next;
                }
            }else if(pre.left==null&&pre.right!=null){
                curhead=pre.right;
                cur = pre.right;
            }
            pre = pre.next;
            //Traversal the next line
            while(pre!=null){                              
                while(pre!=null&&pre.left==null&&pre.right==null){
                    pre = pre.next;
                }
                if(pre == null){
                    break;
                }else if(pre.left!=null){
                    cur.next=pre.left;
                    cur = cur.next;
                    if(pre.right!=null){
                        cur.next = pre.right;
                        cur = cur.next;
                    }
                }else if(pre.left==null&&pre.right!=null){  
                    cur.next= pre.right;
                    cur=cur.next;
                }
                pre=pre.next;
            }
            prehead = curhead;
        }
    }

Log in to reply
 

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