13ms C++ Prefix Sum Hash Table Solution


  • 0
    B

    Same logic as the detailed solution for prefix sum hash table in Java, just implemented in C++.

    I added comments for 2 lines which are not obvious, but critical for the code to work correctly in all edge cases.

    class Solution {
    public:
        int pathSum(TreeNode* root, int sum) {
            unordered_map <int,int> map({{0,1}}); // need to set {0,1} if "sum" = sum of entire path
            return path(root, 0, sum, map);
        }
        int path(TreeNode* root, int pre, int sum, unordered_map<int,int>& map) {
            if (!root) return 0;
            pre+=root->val;
            int out=map[pre-sum]; // need this before incrementing map[pre] to correctly account for "sum" = 0
            map[pre]++;
            out+=path(root->left,pre,sum,map)+path(root->right,pre,sum,map);
            map[pre]--;
            return out;
        }
    };
    

Log in to reply
 

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