18ms Fast One Pass C++ Solution


  • 8
    class Solution {
    public:
        int help(TreeNode* root, int sum, unordered_map<int, int>& store, int pre) {
            if (!root) return 0;
            root->val += pre;
            int res = (root->val == sum) + (store.count(root->val - sum) ? store[root->val - sum] : 0);
            store[root->val]++;
            res += help(root->left, sum, store, root->val) + help(root->right, sum, store, root->val);
            store[root->val]--;
            return res;
        }
    
        int pathSum(TreeNode* root, int sum) {
            unordered_map<int, int> store;
            return help(root, sum, store, 0);
        }
    };
    

  • 0

    @zyoppy008
    Smart solution. It's actually the same as "one dimensional array range sum" problem.


  • 0
    M

    @zyoppy008 thanks for sharing. Are the values stored in the tree changed after the algorithm traverses the tree?


  • 0

    not very understand , would someone please explain it?
    thx a lot


Log in to reply
 

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