Count Downward Stretches With a Given Total
Implement countStretches
You are given the root of a binary tree and an integer target. A stretch is a chain of nodes that goes strictly downward: each node after the first is a child of the node before it. A stretch may start and end at any node — it does not have to include the root or end at a leaf. Return the number of stretches whose values add up to exactly target.
Trying every node as a starting point works but repeats a lot of walking. Prefix sums along the current root-to-node path let you count all stretches that end at a node with a single lookup.
Example 1:
Input: root = [3,2,2,1,null,1], target = 3
Output: 3
Example 2:
Input: root = [0,0,0], target = 0
Output: 5
Example 3:
Input: root = [], target = 4
Output: 0
+ 13 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes ≤ 100 - ●
−100 ≤ node.val ≤ 100; −1000 ≤ target ≤ 1000 - ●
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ●
A stretch is a chain of nodes that goes strictly downward (each next node is a child of the one before). It may start and end at ANY nodes — it need not touch the root or a leaf. Return how many stretches have values adding up to exactly target
root =
target =