18ms Fast One Pass C++ Solution

  • 8
    class Solution {
        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);
            res += help(root->left, sum, store, root->val) + help(root->right, sum, store, root->val);
            return res;
        int pathSum(TreeNode* root, int sum) {
            unordered_map<int, int> store;
            return help(root, sum, store, 0);

  • 0

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

  • 0

    @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.