Path Sum III
Medium · Trees · Tree · Depth-First Search · Binary Tree · Prefix Sum · Hash Table
Problem
Given the root of a binary tree and an integer targetSum, return the number of paths whose node values add up to targetSum.
A path does not have to start at the root or end at a leaf, but it must go downward, from a node to one of its descendants, parent to child at each step. A single node counts as a path.
Examples
Input: root = [5,3,-2,2,-1,None,4], targetSum = 7 Output: 2
The downward paths 5 -> 3 -> -1 and 5 -> -2 -> 4 both sum to 7.
Input: root = [1,-1,1,1], targetSum = 1 Output: 4
Each of the three nodes holding 1 is a path, and so is 1 -> -1 -> 1 down the left side.
Input: root = [], targetSum = 0 Output: 0
With no nodes there are no paths, even for a target of 0.
Constraints
- The tree has between 0 and 1000 nodes
- -10^9 <= Node.val <= 10^9
- -1000 <= targetSum <= 1000
Approaches
- Baseline: every start node, every downward path — time O(n · h), O(n²) worst, space O(h)
Follow-up
The prefix-sum map is the tree version of counting subarrays with sum k: a root-to-node path is an array, and the map holds the prefixes of exactly that array because each node removes its prefix on the way out. Sums can exceed 32 bits (1000 values of 10^9), so Java, C++ and Go keep them in 64-bit integers. The use cases count paths whose sum is divisible by k and find the longest path with the target sum.
Related problems
Start free on Cariara · Coding problems · System design studio
