C++ constant space with details by separating different moves into individual functions.


  • 0
    Y

    To start off, you need to have a function called next_level, This returns the leftmost node of the next level, using the leftmost node of current level, , either left subtree or right subtree, or nextlevel of cur->next , i.e.

     TreeLinkNode* nextlevel( TreeLinkNode* root){
            if(!root)
                return NULL; 
            if(root->left)
                return root->left;
            if(root->right)
                return root->right;
            return nextlevel(root->next);    
        }
    

    So, by calling this function, you can do level order traversal, until no deeper to go.

    Then, you need another function, right_next, to give you the next node of current one. Note the input is the parent's next of current node, i.e.

      TreeLinkNode* rightnext(TreeLinkNode* root){
            if(!root)
                return NULL;
            while(root){
                if(root->left)
                    return root->left;
                if(root->right)
                    return root->right;
                root=root->next;    
            }
            return root;
        }
    
    

    With these two in hand, you can finish it by

     void connect(TreeLinkNode *cur) {
             while( cur ){
                TreeLinkNode* root = cur;
                while(root){
                    if(root->left){
                        if(root->right)
                            root->left->next=root->right;
                        else
                            root->left->next = rightnext(root->next);
                    }
                    if(root->right){
                        root->right->next = rightnext(root->next);
                    }
                    root=root->next;
                }    
                cur=nextlevel(cur);
            }
        }
    

Log in to reply
 

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