355. Path Sum III
You are given the root of a binary tree and an integer targetSum. Count how many downward paths in the tree have values summing to targetSum, and return that count.
A path here is any chain of one or more nodes where each step goes from a node to one of its children. It does not have to start at the root or end at a leaf — it can begin and end anywhere — but it always travels downward, never back up or sideways.
Node values may be negative, so a path's running sum can dip below the target and come back.
Example 1:
Input: root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], targetSum = 8
Output: 3
Explanation: Three downward chains reach 8: 5 → 3, 5 → 2 → 1, and -3 → 11.
Example 2:
Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1], targetSum = 22
Output: 3
Explanation: 5 → 4 → 11 → 2, 4 → 11 → 7, and 5 → 8 → 4 → 5 each sum to 22.
Constraints:
- The number of nodes is in the range [0, 1000].
- -10⁹ ≤ Node.val ≤ 10⁹
- -10¹² ≤ targetSum ≤ 10¹²
- Path sums can exceed 32-bit range — accumulate in 64 bits.
Hints:
A direct plan: every node can be the top of a path, so run a second DFS downward from each node, accumulating the sum and counting every time it hits the target. That is O(n²) in the worst case but perfectly correct.
To do it in one pass, think in prefix sums along the root-to-current chain: a downward path ending at the current node sums to targetSum exactly when some ancestor prefix equals currentPrefix − targetSum. Carry a hash map counting the prefixes on the current chain (seed it with {0: 1}), and un-count each prefix when you backtrack out of its subtree.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], targetSum = 8
Expected output: 3