Binary Tree Cameras
You are given the root of a binary tree. We install cameras on the nodes of the tree. Each camera at a node can monitor its parent, itself, and its children. Find the minimum number of cameras needed to monitor all nodes of the tree.
Constraints:
- The number of nodes in the tree is in the range [1, 1000].
- Node.val is 0.
Examples:
Input: [1,null,2,0,null,0,4]
Output: 2
Explanation: One possible solution is to install cameras at nodes 0 and 4.
Solutions
Depth-First Search
Time: O(N)Space: O(H)
We use a depth-first search to traverse the tree. For each node, we have three states: -1 (not covered), 0 (covered by children), and 1 (has camera). If a node is not covered by its children, we install a camera at the current node and increment the answer.
class Solution {
int ans;
public int minCameraCover(TreeNode root) {
ans = 0;
if (dfs(root) == -1) ans++;
return ans;
}
private int dfs(TreeNode node) {
if (node == null) return 0;
int left = dfs(node.left),Question and saidQuestion and = dfs(node.right);
if (left == -1 || right == -1) {
ans++;
return 1;
}
if (left == 1 || right == 1) return 0;
return -1;
}
}Follow-up:
What if we can install cameras on the edges of the tree instead of the nodes?
