[summary-of-all-concise-solution]C++ implementation with detail comments


  • 1

    Recursive Solution method -1-

    class Solution {
    public:
        int sumNumbers(TreeNode* root) {
            if(!root)   return 0;
            return help(root, 0);
        }
        /*** return value : the root-leaf-sum-of-cur_root  ***/
        int help(TreeNode* root, int val){
            /***  leaf node   ***/
            if(!root->left && !root->right)
                return 10*val+root->val;
            int result=0;
            if(root->left)
                result+=help(root->left, 10*val+root->val);
            if(root->right)
                result+=help(root->right,10*val+root->val);
            return result;
        }
    };
    

    A more concise solution

    class Solution {
    public:
        int sumNumbers(TreeNode* root) {
            return help(root, 0);
        }
        
        int help(TreeNode* root, int val){
            if(!root)   return 0;
            val=10*val+root->val;
            if(!root->left && !root->right) return val;
            return help(root->left, val)+help(root->right, val);
        }
    };
    

    Non-Recursive-Solution

    class Solution {
    public:
        int sumNumbers(TreeNode* root) {
            int result=0;
            /*** use the (q, sumq) to record the cur-sum-value of the cur-node pair-wisely ***/
            queue<TreeNode*> q;
            queue<int> sumq;
            if(root!=NULL){
                q.push(root);
                sumq.push(root->val);
            }
            while(!q.empty()){
                TreeNode* cur=q.front();
                q.pop();
                int cur_sum=sumq.front();
                sumq.pop();
                /***   only add the root-cur-sum-value  ***/
                if(!cur->left && !cur->right)
                    result+=cur_sum;
                else{
                    if(cur->left){
                        q.push(cur->left);
                        sumq.push(10*cur_sum+cur->left->val);
                    }
                    if(cur->right){
                        q.push(cur->right);
                        sumq.push(10*cur_sum+cur->right->val);
                    }
                }
            }
            
            return result;
        }
    };

Log in to reply
 

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