Path Sum III

Medium

Given the root of a binary tree and an integer targetSum (passed as k), return the number of downward paths (parent to child, any start and end node) whose node values sum to k.

Example 1

Input:  root = [10,5,-3,3,2,null,11,3,-2,null,1], k = 8
Output: 3

Example 2

Input:  root = [5,4,8,11,null,13,4,7,2,null,null,5,1], k = 22
Output: 3

Constraints

• 0 <= number of nodes <= 1000
• -10^9 <= Node.val <= 10^9
• -1000 <= k <= 1000