571. Binary Tree Cameras
You are given the root of a binary tree (every node's value is 0 — the values carry no information). You may install a camera on any node. A camera placed on a node watches three places at once: the node itself, its parent, and its immediate children.
Return the minimum number of cameras needed so that every node in the tree is watched by at least one camera.
A node with no children still needs coverage, and a camera never sees past one edge — grandparents and grandchildren are out of range.
Example 1:
Input: root = [0, 0, null, 0, 0]
Output: 1
Explanation: The root's left child touches everything: a single camera there watches itself, its parent (the root), and both of its children.
Example 2:
Input: root = [0, 0, null, 0, null, 0, null, null, 0]
Output: 2
Explanation: The tree is a downward path of five nodes. One camera can watch at most three consecutive path nodes, so two cameras are necessary — and placing them one edge above each end suffices.
Constraints:
- 1 ≤ number of nodes ≤ 1000
- Node.val == 0 for every node
Hints:
Think bottom-up. A camera on a leaf watches only the leaf and its parent; a camera on the leaf's PARENT watches the parent, the leaf, the other child, and the grandparent — strictly more. So an optimal solution never needs a camera on a leaf.
Do a post-order DFS where every node reports one of three states to its parent: 0 = I am not covered yet, 1 = I am covered but hold no camera, 2 = I hold a camera. Treat missing children as state 1.
Place a camera exactly when some child reports state 0 — that child can no longer be covered by anyone else. After the traversal, check whether the root itself ended in state 0 and add one final camera if so.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [0, 0, null, 0, 0]
Expected output: 1