O(N) approach to Path sum 3

class Solution {
public:
    int get(TreeNode *root, int t, map<long long, int> &mp, long long pr = 0) {
        if (root == nullptr) return 0;
        pr += root->val;
        int ans = mp[pr - t];
        mp[pr]++;

        // Recursively calculate the count of paths for left and right subtrees
        ans += get(root->left, t, mp, pr);
        ans += get(root->right, t, mp, pr);

        // Decrement the frequency of the current prefix sum (backtrack)
        mp[pr]--;
        return ans;
    }

    int pathSum(TreeNode* root, int targetSum) {
        map<long long, int> mp;
        mp[0] = 1;
        return get(root, targetSum, mp);
    }
};