#217HardTrees· Tree DP with Three Coverage States

Minimum Monitors in a Corridor Tree

A research station is a network of rooms connected by corridors with no cycles, laid out as a binary tree: every room has at most two rooms below it. A security monitor installed in a room watches that room, the room directly above it (its parent) and the rooms directly below it (its children). Every room must be watched by at least one monitor. Given the root of the tree, return the minimum number of monitors needed.

Input format

`root`: the tree as a level-order array, where `null` marks a missing child. The values themselves carry no meaning.

Output format

A single integer: the minimum number of monitors.

Examples

Input: root = [0, 0, null, 0, 0]

Output: 1

The tree has four rooms: the root, its only child and the two children of that child. One monitor in the child of the root watches its parent (the root), itself and both of its children, so one monitor is enough.

Input: root = [0, 0, null, 0, null, 0, null, null, 0]

Output: 2

This is a corridor of five rooms in a row. Monitors in the second and the fourth room together watch all five, and one monitor cannot.

Input: root = [0]

Output: 1

A single room is its own tree and needs a monitor to be watched.

Constraints

1 <= number of rooms <= 1000
Every node value is 0.

#tree
#dynamic-programming
#greedy
#dfs
#post-order