A recursive solution without the (common) while loop in the end of the function


  • 0
    B

    This code doesn't require to loop to the end of the flatten branch in order to find the last element . Instead, there's a sub function that returns the end of the branch after flattening.

        void flatten(TreeNode* root) {
            _flatten(root);
    
        }
    private: 
        TreeNode* _flatten(TreeNode* root)
            {
                if(root == NULL)
                    return NULL;
                    
            if(root->left == NULL && root->right==NULL)
            {
                return root;
            }
    
            
            if(root->left != NULL)
            {
                TreeNode* end = _flatten(root->left);
                TreeNode* end2 =_flatten(root->right);
                
                end->right = root->right;
                root->right=root->left;
                root->left=NULL;
    
                if(end2 != NULL)
                    return end2;
                else 
                    return end;
            }
            else
            {
                 return _flatten(root->right);
            }
        
            }  
    

Log in to reply
 

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