Path Sum III

Intuition

A downward path from an ancestor A to the current node C sums to targetSum exactly when the running total at C minus the running total just above A equals targetSum. That means the number of valid paths ending at C is how many ancestors have a prefix sum equal to currentPrefix - targetSum. We keep a hash map counting how often each prefix sum appears along the current root-to-node chain, seeded with a count of one for the empty prefix zero so that paths starting at the root are counted. As we descend we add the lookup, register our own prefix, recurse, and then decrement our prefix on the way back up so it does not leak into unrelated branches. Because node values can be large, the prefix sums use 64-bit arithmetic to avoid overflow.

Algorithm walkthrough

1. 1Initialize a hash map count with {0: 1}, representing the empty prefix before the root.
2. 2DFS from the root carrying prefix, the sum of values from the root down to the current node.
3. 3At each node add node.val to prefix, then add count[prefix - targetSum] to the answer.
4. 4Increment count[prefix] to make this node's prefix available to its descendants.
5. 5Recurse into both children, then decrement count[prefix] before returning to undo this node's contribution.
6. 6Return the accumulated count of qualifying paths.

Implementation

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        count = {0: 1}
        self.total = 0

        def dfs(node: Optional[TreeNode], prefix: int) -> None:
            if not node:
                return
            prefix += node.val
            self.total += count.get(prefix - targetSum, 0)
            count[prefix] = count.get(prefix, 0) + 1
            dfs(node.left, prefix)
            dfs(node.right, prefix)
            count[prefix] -= 1

        dfs(root, 0)
        return self.total