18ms Fast One Pass C++ Solution


  • 7
    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?


Log in to reply
 

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