Fewest Cameras
You are given the root of a binary tree. A camera placed on a node watches that node, its parent and its children.
Return the fewest cameras needed so that every node is watched. The values in the nodes do not matter.
Trees appear in the tests in level order, with null for a missing child, like [3,9,20,null,null,15,7]. Each node is a TreeNode with .val, .left and .right; the class is already defined for you.
Example 1
root [1,2,3]
returns 1
A camera on the root watches all three nodes.
Example 2
root [1,2,null,3,null,4]
returns 2
A chain of four. One camera reaches at most three nodes in a row, so two are needed.
Example 3
root [7]
returns 1
A single node still needs a camera.
Constraints
1 <= number of nodes <= 400 <= node.val <= 9
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.