Solution


  • 0
    S

    This solution traverses the tree level by level and keep track of prev node in each level.

    '''

     public void connect(TreeLinkNode root) {
        
        if (root == null) {
            return;
        }
    
        TreeLinkNode parent = root;
        TreeLinkNode pre;
        TreeLinkNode next;
        while (parent != null) {
            //pre keep track of horizontal nodes
            pre = null;
            
            //first node in the next level
            next = null;
            
            //basically traverse level by level
            while (parent != null) {
                if (next == null){
                    next = (parent.left != null) ? parent.left: parent.right;
                }
    
                if (parent.left != null){
                    //if in this level there's pre
                    if (pre != null) {
                        pre.next = parent.left;
                        pre = pre.next;
                    } else {
                        pre = parent.left;
                    }
                }
    
                if (parent.right != null) {
                    if (pre != null) {
                        pre.next = parent.right;
                        pre = pre.next;
                    } else {
                        pre = parent.right;
                    }
                }
                //same level, horizontally get the next node
                parent = parent.next;
            }
            
            parent = next;
        }
        
    }
    

    '''


Log in to reply
 

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