You may install cameras on nodes of a binary tree. A camera watches its own node, its parent, and its direct children.
Write min_camera_cover(root: TreeNode) -> int: the fewest cameras so that every node is watched. TreeNode(val, left=None, right=None) is in the starter; node values don't matter.
Examples:
- A single node needs
1camera. - A root with one child, which has two children of its own, needs
1(put it on the middle node). - A straight chain of 5 nodes needs
2(on the 2nd and 5th, or on the 2nd and 4th).
Constraints: 1 to about 130,000 nodes; the big test is a balanced tree. Anything that tries sets of nodes is hopeless.
Aim for O(n).
Show hint
Think bottom-up. Is a camera on a leaf ever better than one on the leaf's parent? From there, what does each node need to know about its children to decide whether it must hold a camera?