You get the root of a binary tree and an integer targetSum. A downward path starts at any node and moves only from a parent to one of its children, stopping at any node along the way. It doesn't have to start at the root or end at a leaf, and a single node counts as a path.
Return how many downward paths have values that add up to targetSum.
The three paths are 6 → 2 → -1, 6 → -3 → 4 and 6 → 2 → 3 → -4. The last one shows that a path can run through a negative value and still land on the target.
3 → -3 and -3 → 3 both sum to 0, and so does the lone node 0. The first two share a node: paths may overlap.
Constraints
0 and 1000 nodes.-10⁹ <= Node.val <= 10⁹-1000 <= targetSum <= 1000Along one root-to-node path, a downward path ending at the current node is a stretch at the bottom of it. Its sum is the running total from the root minus the running total at the node just above where it starts.
3