Simple C++ using recursion


  • 0
    C

    Running total is incremented when moving down into child nodes. Then the sum of the running totals are added up when leaf nodes are reached. The total of those individual sums is added up through recursive returns.

    class Solution{
    public:
        
        
        int sumNumbers(TreeNode* root){
            
            return sumNumbersHelper(root, 0);
        }
    
        int sumNumbersHelper(TreeNode* root, int running_total){
            
            /*
             
             base case: NULL node or leaf node
             
             */
            if (!root){
                return 0;
            }
            if (!root->left && !root->right){
                return running_total + root->val;
            }
            
            /*
             
             recursive case: multiply running total by ten to make space for child value
             
             example:
             
             1        ==>   10 * (0+1) = 10      ( recursive case )
              \
               2        ==>   10 * (10+2) = 120  ( recursive case )
                \
                 3        ==>    120 + 3         ( base case )
             
             */
            running_total = 10 * ( running_total + root->val );
            return
                  sumNumbersHelper(root->right, running_total)
                + sumNumbersHelper(root->left, running_total);
            
            
        }
    };
    

Log in to reply
 

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