hardTreesPure DSA~40 min
Minimum Cameras to Monitor a Facility Tree
A facility is laid out as a binary tree of rooms. A camera placed in a room monitors that room, its parent, and its immediate children. Place the fewest cameras so every room is monitored.
Problem
Given the root of a binary tree, install cameras on tree nodes. Each camera monitors its own node, its parent, and its direct children. Return the minimum number of cameras needed so that all nodes are monitored.
Input
The root of a binary tree. Node count in [1, 1000]; node values are irrelevant to the answer.
Output
An integer: the minimum number of cameras.
Constraints
- 1 <= number of nodes <= 1000
- Each camera covers node + parent + children only (radius 1).
Examples
Example 1
Input
[0,0,null,0,0]
Output
1
One camera at the only node with two children covers the root and both leaves.
Example 2
Input
[0,0,null,0,null,0,null,null,0]
Output
2
A left-skewed chain of 5 nodes needs two cameras.