Watching every branch
Place the fewest cameras in a tree so that every node is watched, where a camera watches its parent, itself and its children, using three states per node. About 22 minutes.
Three states
A camera at a node watches that node, its parent and its children. Work from the leaves up. Each subtree reports one of three states about its top node: zero if the node is not watched, one if it holds a camera, and two if it is watched by a camera below.
An empty child counts as watched, state two, so that it asks for nothing.
NOT_COVERED, COVERED, HAS_CAMERA = 0, 1, 2
- cameras
- 0
The two leaves are not watched: state 0 each.
Camera on the parent
If either child is not watched, this node must hold a camera, because only a camera here or on the child could watch it, and a camera on the parent also watches the grandparent. Add a camera and report state one.
Otherwise, if either child holds a camera, this node is watched: report state two. If neither applies, this node is not watched: report state zero and let the parent deal with it. At the root, state zero needs one more camera.
if state == NOT_COVERED:
cameras += 1Why not put cameras on the leaves?
- AA camera on the leaf's parent watches the leaf and also the grandparent and siblings
- BCameras do not work on leaves
- CLeaves are cheaper to cover
Show the answer
A camera on the leaf's parent watches the leaf and also the grandparent and siblings. It covers at least as much as a camera on the leaf would.
Binary tree cameras
You install cameras on the nodes of a binary tree. A camera at a node monitors that node, its parent and its children. Given the root of a binary tree, return the minimum number of cameras needed to monitor every node.
root = [0, 0, null, 0, 0] → 1
1 ≤ number of nodes ≤ 1,000