Show problems as
Classic problem #968HardDynamic ProgrammingTreeDepth-First SearchBinary TreeDP on Trees

Binary Tree Cameras

Real-world version: Fewest Duct Sensors
Tracked in this browser only
Read Binary Tree Cameras on LeetCode(opens in a new tab)

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

An air-duct network runs out from a single plant-room junction. Every junction splits into at most two junctions further along the network, one on its left branch and one on its right branch.

Because the harness passes plain JSON, the network arrives as junctions, a listing written depth by depth. junctions[0] stands for the plant-room junction. After it the entries come in pairs, giving the left branch and then the right branch of each junction already written out, taken in that same order. A branch that carries no junction is written null, and a null claims no pair of its own; trailing null entries are left off the end. Only the shape of the network matters here, so every entry that stands for a junction is written 0.

A sensor fitted at a junction watches that junction, the junction immediately upstream of it, and every junction immediately downstream of it. Nothing further away is watched.

Return the fewest sensors that leave every junction in the network watched.

Examples

Example 1

Input
junctions = [0, 0, null, 0]
Output
1

The network is a chain of three junctions. A sensor at the middle one watches the plant-room junction upstream of it, itself, and the junction downstream of it, so one sensor covers all three.

Example 2

Input
junctions = [0]
Output
1

A lone junction still has to be watched, and the only place to fit a sensor is that junction itself.

Example 3

Input
junctions = [0, 0, null, 0, null, 0]
Output
2

The network is a chain of four junctions. A sensor on the second junction watches the first three, and a sensor on the fourth watches itself, which leaves nothing unwatched.

Constraints

  • 1 <= number of junctions <= 1000
  • Every entry of junctions is either 0 or null
  • junctions[0] == 0
  • 1 <= junctions.length <= 2001

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 fewest_sensors(junctions: list) -> int:
Java
public int fewestSensors(Integer[] junctions)

More on the same topics