492. Watchtower Cover
A mountain valley has outposts connected by trails that form a binary tree rooted at root. You may build a watchtower on any outpost. A tower watches its own outpost, the outpost directly above it (its parent) and the outposts directly below it (its children), but nothing farther away.
Return the minimum number of watchtowers needed so that every outpost in the valley is watched by at least one tower. The values stored in the nodes carry no meaning and are always 0; only the shape of the tree matters.
Example 1
- Input:
- root = [0,0,0,0,null,null,0]
- Output:
- 2
- Explanation:
Towers on the two children of the root watch the root and the two grandchildren as well, so 2 towers suffice and one is not enough.
Example 2
- Input:
- root = [0,0,0,null,0,null,0,null,0]
- Output:
- 2
- Explanation:
A tower on the right child of the root's left child watches that whole three-node chain, and a tower on the root's right child watches the root and its own branch, so 2 towers suffice.
Constraints
1 ≤ number of nodes ≤ 105
Node.val == 0
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)