Path Sum III
mediumTrees & BST II+20 XPTime limit 2s
Count the downward paths whose values add up to target. A downward path starts at any node and goes only from parents to children, ending at any node below it (or at the start node itself). It does not have to start at the root or end at a leaf.
Tree format. A binary tree is given on one line in level order (top to bottom, left to right), with null for a missing child — the same way most interview platforms show trees. Trailing nulls are left out, and an empty tree is the single word null. Example: 3 9 20 null null 15 7 is
3
/ \
9 20
/ \
15 7
Input: one tree, then a line target.
Output: the number of such paths.
Constraints: 0 ≤ nodes ≤ 10⁴, −1000 ≤ value ≤ 1000, −10⁵ ≤ target ≤ 10⁵. The tree has at most 10⁴ nodes and its height is at most 500, so recursion is safe in every language.
Think about it: trying every start node and walking down is O(n·h). Faster: the same trick as "subarray sum equals k". Keep the prefix sums from the root to the current node in a hash map; the number of paths ending here is the count of earlier prefixes equal to prefix − target. Remember to remove the current prefix when you go back up.
Sample input 1
10 5 -3 3 2 null 11 3 -2 null 1 8
Sample output 1
3
Sample input 2
1 -1 1 -1 1 0
Sample output 2
2
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).