TreePrefix SumDFSHash Map
Count the downward paths in a binary tree whose node values add up to a target. A path may start and end at any node, but it must only go from a parent down to a child. Build the tree from the level-order input yourself, then solve the problem.
Input
Line 1: the tree in level order with null for missing children. Line 2: the target sum.
Output
Print the number of such paths.
Constraints
1 <= number of nodes <= 1000 -100 <= value <= 100 -1000 <= target <= 1000
Example 1
Input
10 5 -3 3 2 null 11 3 -2 null 1 8
Output
3
The paths 5-3, 5-2-1 and -3-11 each sum to 8.