hardTreesPure DSA~30 min
All Root-to-Leaf Paths Summing to a Target
Enumerate every root-to-leaf path whose node values add up to a target total.
Problem
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values equals targetSum. Each path is the list of node values from root to leaf.
Input
A binary tree root and an integer targetSum.
Output
A list of qualifying root-to-leaf value paths.
Constraints
- 0 <= number of nodes <= 5000
- -1000 <= node value, targetSum <= 1000
- A path must end at a leaf.
Examples
Example 1
Input
root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output
[[5,4,11,2],[5,8,4,5]]
Two root-to-leaf paths sum to 22.
Example 2
Input
root = [1,2,3], targetSum = 5
Output
[]
No root-to-leaf path sums to 5.