Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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);
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement