474. Downward Target Paths
A warehouse stores its stock in a binary tree of shelves. Each shelf holds an integer balance, which may be negative to represent a pending return. An inspector may start at any shelf and then walk only downward, moving from a shelf to one of its children, and may stop at any shelf at or below the start. The walk's total is the sum of the balances of every shelf visited, including the first and the last.
Given root and the number target, return how many such downward walks have a total exactly equal to target. A walk made of a single shelf counts, walks need not touch the root or end at a leaf, and two walks are different when their start shelf or end shelf differs. An empty tree has no walks. The answer is guaranteed to fit in a 32-bit signed integer.
Example 1
- Input:
- root = [9,4,-2,1,3,null,6,2,-4,null,5], target = 7
- Output:
- 3
- Explanation:
The downward walks adding up to 7 are [9 -> -2], [4 -> 1 -> 2], [4 -> 3], so the answer is 3.
Example 2
- Input:
- root = [4,4,null,4,null,4], target = 8
- Output:
- 3
- Explanation:
The downward walks adding up to 8 are [4 -> 4], [4 -> 4], [4 -> 4], so the answer is 3.
Example 3
- Input:
- root = [-2,null,-3,1,null,-1], target = -3
- Output:
- 2
- Explanation:
The downward walks adding up to -3 are [-3], [-3 -> 1 -> -1], so the answer is 2.
Constraints
0 ≤ number of nodes ≤ 105
-1000 ≤ Node.val ≤ 1000
-1010 ≤ target ≤ 1010
The answer fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)