Description
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.
Examples
Input:
root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22Output:
[[5,4,11,2],[5,8,4,5]]Explanation:
Two paths sum to 22.
Input:
root = [1,2,3,4,5], targetSum = 8Output:
[[1,2,5]]Explanation:
There is only one root-to-leaf path with sum 8: 1->2->5 (1+2+5=8). The path 1->3 sums to 4, and 1->2->4 sums to 7.
Input:
root = [10,-3,5,2,null,null,6,-2,null,null,7], targetSum = 14Output:
[[10,-3,2,-2],[10,5,6,7]]Explanation:
Two root-to-leaf paths sum to 14: 10→(-3)→2→(-2) and 10→5→6→7. The sums are 10+(-3)+2+(-2) = 7 and 10+5+6+7 = 28, so the paths matching targetSum=14 depend on the tree structure.
Constraints
- •
0 ≤ number of nodes ≤ 5000 - •
-1000 ≤ Node.val ≤ 1000 - •
-1000 ≤ targetSum ≤ 1000