C++ solution with prefix sum stored in hash table


  • 3
    Y

    The idea is simple: along the path, record all prefix sums in a hash table. For current prefix sum x, check if (x - target) appears in the hash table.

    class Solution {
    public:
        int pathSum(TreeNode* root, int sum) {
            unordered_map<int, int> m;
            m[0]++;
            
            int total = 0;
            helper(root, 0, sum, total, m);
            return total;
        }
        
        void helper(TreeNode *p, int cur, int sum, int &total, unordered_map<int, int> &m) {
            if (!p) return;
            
            cur += p->val;
            if (m.find(cur - sum) != m.end()) total += m[cur - sum];
            m[cur]++;
            
            helper(p->left, cur, sum, total, m);
            helper(p->right, cur, sum, total, m);
            
            m[cur]--;
        }
    };
    

  • 0
    A
    This post is deleted!

  • 0

    @yicui clever solution, instead of checking if sum exist, it notes down all the prefixSum and checks if current prefixSum - sum exists. TraceBack is also used in this solution.


Log in to reply
 

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