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 {
public:
int minCameraCover(TreeNode* root) {
int ans = 0;
function<int(TreeNode*)> dfs = [&](TreeNode* node) {
if (!node) return 0;
int left = dfs(node->left);
int right = dfs(node->right);
if (left == -1 || right == -1) {
ans++;
return 1;
}
if (left == 1 || right == 1) return 0;
return -1;
}
;
if (dfs(root) == -1) ans++;
return ans;
}
}
;Follow-up:
What if we can install cameras on the edges of the tree instead of the nodes?
