C++ Solution, one pass, very easy to understand with explanation


  • 1
    E

    The idea is simple.
    For every node S, keep a vector to record all sum start from node S

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
    
        vector<int> solver(TreeNode * root, int sum, int & count){
            if(root==NULL) return {};
            vector<int> left = solver(root->left,sum,count);
            vector<int> right = solver(root->right,sum,count);
            vector<int> res;
            res.push_back(root->val);
            if(root->val==sum) count++;
            for(int i = 0; i < left.size(); i++){
                int num = left[i] + root->val;
                if(num == sum) count++;
                res.push_back(num);
            }
            for(int i = 0; i < right.size(); i++){
                int num = right[i] + root->val;
                if(num == sum) count++;
                res.push_back(num);
            }
            return res;
        }
    
        int pathSum(TreeNode* root, int sum) {
            if(root==NULL) return 0;
            int count = 0;
            solver(root,sum,count);
            return count;
        }
    };
    

Log in to reply
 

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