Python DFS Prefix Sum Solution Explained Easily
IntuitionWe use a prefix sum approach for efficiency. The prefix sum records the cumulative sum of nodes from the root to the current node. By using a hashmap t
# Intuition
We use a **prefix sum** approach for efficiency. The prefix sum records the cumulative sum of nodes from the root to the current node. By using a hashmap to store these sums, we can efficiently check if a subpath exists with the required sum.

# Approach
Steps
1. **Recursive traversal**: Perform a depth-first traversal of the tree.
2. **Track cumulative sums**: Keep track of the cumulative sum as you traverse the tree.
3. **Use a hashmap**: Store how many times each cumulative sum has been encountered so far.
4. **Check for valid paths**:
    - If `currentSum - targetSum` exists in the hashmap, it means there's a subpath that sums to targetSum.
5. **Backtrack**: When moving back up the tree (backtracking), decrement the count of the current sum in the hashmap to avoid affecting sibling nodes.

# Complexity
- Time complexity:
$$O(n)$$

- Space complexity:
$$O(n)$$

# Code
```python3 []
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        # Hashmap to store prefix sums and their counts
        prefix_sum_count = {0: 1}  # Base case: one way to have a sum of 0 (no nodes)

        def dfs(node, current_sum) -> int:
            if node is None:
                return 0
            
            current_sum += node.val
            # Count the number of valid paths ending at the current node
            # Our found path = targetSum = current_sum - prefix_sum
            num_paths = prefix_sum_count.get(current_sum - targetSum, 0)

            # Update the hashmap with the current cumulative sum
            prefix_sum_count[current_sum] = prefix_sum_count.get(current_sum, 0) + 1

            # Recurse down to the left and right children
            num_paths += dfs(node.left, current_sum)
            num_paths += dfs(node.right, current_sum)
            
            # Backtrack - remove the current cumulative sum from the hashmap
            prefix_sum_count[current_sum] -= 1
            
            return num_paths
        
        return dfs(root, 0)
```

# Example
```
       10
      /  \
     5   -3
    / \     \
   3   2     11
  / \   \
 3  -2   1

Using the tree above, with targetSum = 8, let's step through the approach:
Initialization:

    prefix_sum_count = {0: 1} (base case).
    currentSum = 0.

DFS Traversal:

    Visit Node 10:
        currentSum = 10.
        Check: currentSum - targetSum = 10 - 8 = 2 → Not in hashmap.
        Add 10 to hashmap: {0: 1, 10: 1}.

    Go Left to Node 5:
        currentSum = 10 + 5 = 15.
        Check: 15 - 8 = 7 → Not in hashmap.
        Add 15 to hashmap: {0: 1, 10: 1, 15: 1}.

    Go Left to Node 3:
        currentSum = 15 + 3 = 18.
        Check: 18 - 8 = 10 → Found in hashmap (1 occurrence).
        This means there’s 1 valid path: [5, 3].
        Add 18 to hashmap: {0: 1, 10: 1, 15: 1, 18: 1}.

    Go Left to Node 3 (leaf):
        currentSum = 18 + 3 = 21.
        Check: 21 - 8 = 13 → Not in hashmap.
        Add 21 to hashmap: {0: 1, 10: 1, 15: 1, 18: 1, 21: 1}.
        Backtrack: Remove 21 → {0: 1, 10: 1, 15: 1, 18: 1}.

    Go Right to Node -2:
        currentSum = 18 - 2 = 16.
        Check: 16 - 8 = 8 → Not in hashmap.
        Add 16 to hashmap: {0: 1, 10: 1, 15: 1, 18: 1, 16: 1}.
        Backtrack: Remove 16 → {0: 1, 10: 1, 15: 1, 18: 1}.

    Backtrack to Node 5:
        Remove 18 → {0: 1, 10: 1, 15: 1}.

... (and so on for the rest of the tree). ```
['Hash Table', 'Depth-First Search', 'Python3']