FunctionRacerProblemsRace

Fewest Cameras

HardTreesPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Trees problems