Fewest Monitors to Watch a Tree
A binary tree is given as a level-order array: tree[0] is the root, then the children of each real node are listed left to right, level by level. A missing child is written as null, and the children of a missing node are not listed at all. For example [1,2,3,null,4] is root 1 with children 2 and 3, where 2 has only a right child 4.
The tree is a network of offices (every value is 0; only the shape matters). A monitor installed in an office watches that office, its parent and its children.
Return the minimum number of monitors so that every office is watched. An empty tree needs 0 monitors.
Example 1
Input: tree = [0,0,null,0,0] Output: 1 Explanation: One monitor on the left child watches the root and both grandchildren.
Example 2
Input: tree = [0,0,null,0,null,0,null,null,0] Output: 2 Explanation: The chain needs monitors on the 2nd and 4th offices.
Constraints
- 0 <= number of nodes <= 8000
- Every value is 0.
Hint 1
Decide bottom-up: a leaf should never hold a monitor if its parent can hold one instead.
Hint 2
Give every node a state (not watched / watched / has monitor) computed from its children; a node with an unwatched child must get a monitor.
Discussion 0
Join free to post in the discussion.
Good practice for: Site Reliability Engineer, DevOps Engineer, Backend Developer, Cloud Engineer, Embedded Systems Engineer
Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.