Recursive solution in (with constant space ?) C++


  • 0
    U

    Would this be considered constant space? I am not using any local variables inside the recursion.

    class Solution {
    public:
        void findSum(TreeNode *root, int &cur_sum, int &final_sum)
        {
            if(root == NULL)
                return;
            
            cur_sum= cur_sum*10 + root->val;
            
            if(root->left==NULL && root->right == NULL)
            {
                final_sum+= cur_sum;
                cur_sum = (cur_sum-root->val)/10;
                return;
            }
            
            if(root->left) findSum(root->left, cur_sum, final_sum);
            if(root->right) findSum(root->right, cur_sum, final_sum);
            cur_sum = (cur_sum - root->val)/10;
        }
        
        int sumNumbers(TreeNode* root) {
            int cur_sum = 0;
            int final_sum = 0;
            findSum(root, cur_sum, final_sum);
            return final_sum;
        }
    };
    

Log in to reply
 

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