C++ solution with prefix sum stored in hash table

  • 3

    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 {
        int pathSum(TreeNode* root, int sum) {
            unordered_map<int, int> m;
            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];
            helper(p->left, cur, sum, total, m);
            helper(p->right, cur, sum, total, m);

  • 0
    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.