13ms C++ Prefix Sum Hash Table Solution

  • 0

    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 {
        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;
            int out=map[pre-sum]; // need this before incrementing map[pre] to correctly account for "sum" = 0
            return out;

Log in to reply

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