Simple DFS + Prefix Sum | C++ | Easy |
IntuitionWe use a DFS (Depth First Search) traversal and maintain a prefix sum map to keep track of the cumulative sum from the root to the current node.Approac
# Intuition
We use a DFS (Depth First Search) traversal and maintain a prefix sum map to keep track of the cumulative sum from the root to the current node.

# Approach
1. Use a Hash Map (prefixSumCount)
    1. Key: Stores the prefix sum encountered at different nodes.
    2. Value: Stores the count of occurrences of that prefix sum.
DFS Traversal

2. Start DFS traversal from the root.
    1. Compute the currentPrefixSum at each node.
    1. Check if (currentPrefixSum - targetSum) exists in prefixSumCount.
    1. If it does, it means that a valid path ending at the current node has a sum equal to targetSum.
    1. Store the current prefix sum in prefixSumCount.
    1. Recurse into left and right children.
    1. Backtrack after visiting children (to remove the effect of this node for other paths).

# Complexity
- Time complexity: O(N)

- Space complexity: O(N) worst case(hash map)

# Code
```cpp []
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int solve(TreeNode* root, long long sum, int target, unordered_map<long long, int> &mpp) {
        if(!root) return 0;
        sum += root->val;
        int count = mpp[sum - target];
        mpp[sum]++;
        count += solve(root->left, sum, target, mpp);
        count += solve(root->right, sum, target, mpp);
        mpp[sum]--;


        return count;
    }
    int pathSum(TreeNode* root, int target) {
        unordered_map<long long, int> mpp;
        mpp[0] = 1;
        return solve(root, 0, target, mpp);
    }
};
```
['Depth-First Search', 'Prefix Sum', 'C++']