Path Sum III
The key idea
Any downward path equals the difference of two root-to-node running sums. Walk the tree once, keep the running sum from the root, and at each node count how many earlier prefix sums equal (running sum - targetSum). A hash map of prefix-sum counts turns the O(n^2) double walk into a single O(n) pass.
Problem
Given the root of a binary tree and an integer targetSum, return the number of downward paths whose node.val values add up to targetSum. A path does not need to start at the root or end at a leaf, but it must go downward, moving only from a parent node to one of its child nodes.
Constraints
- The number of nodes in the tree is in the range
[0, 1000]. -10^9 <= Node.val <= 10^9-1000 <= targetSum <= 1000
Examples
Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY