Show problems as
Classic problem #437MediumTreeDepth-First SearchBinary Tree

Path Sum III

Real-world version: Pipeline Stretch Tallies
Tracked in this browser only
Read Path Sum III on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstPath Sum & Root to Leaf · Binary Trees & BST, animated step by step

A slurry pipeline carries material away from a single intake and splits as it goes. Every station on the network shifts the line pressure by a signed figure in kilopascals: positive where a booster pump adds pressure, negative where a filter costs pressure.

The network is handed to you as stations, a listing of the network one depth at a time, left to right. Slot 0 holds the intake. Each station that appears in the listing claims the next two free slots for the lines leaving it, the left line first and the right line second. A slot holding null carries no station and claims no slots of its own. Trailing null slots may be left off, and an empty listing means nothing has been built.

A stretch is one or more stations read off by following the flow: it may begin at any station and every further step must move to a station directly downstream of the one before it. Two stretches count as different unless they cover exactly the same stations.

Given the integer target, return how many stretches have pressure shifts totalling exactly target.

Examples

Example 1

Input
stations = [5, 2, 5], target = 5
Output
2

The intake alone shifts pressure by 5, and the station on the right line alone shifts it by 5. Both are stretches of one station, and no other stretch totals 5.

Example 2

Input
stations = [7, -4, null, 9, 2], target = 12
Output
1

Slot 2 is empty, so the intake has one line leaving it, ending at -4, which itself feeds 9 and 2. The stretch 7, -4, 9 totals 12.

Example 3

Input
stations = [], target = 3
Output
0

No station has been built, so there is no stretch to total.

Constraints

  • 0 <= number of listed stations <= 1000
  • -10^9 <= station pressure shift <= 10^9
  • -1000 <= target <= 1000
  • stations[0] is not null whenever stations is non-empty
  • stations is a valid depth-by-depth listing of one connected network

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def pipeline_stretch_tallies(stations: list[int | None], target: int) -> int:
Java
public int pipelineStretchTallies(Integer[] stations, int target)

More on the same topics