Given the root of a binary tree and an integer target, count the number of downward paths whose values add up to target. A downward path may start at any node and end at any node below it, but it must always move from a parent to a child. A path may consist of a single node.
Examples
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Input: root = build_tree([10, 5, -3, 3, 2, None, 11, 3, -2, None, 1]), target = 8
Output: 3
Explanation: 5->3, 5->2->1 and -3->11 all sum to 8.
Input: root = build_tree([1, 1, 1]), target = 1
Output: 3
Constraints
0 <= number of nodes <= 1000-1000 <= node.val <= 1000,-10**6 <= target <= 10**6
Goals
- Extend the prefix-sum trick from arrays to root-to-node paths
- Undo a bookkeeping change when a recursive call returns