968. Binary Tree Cameras
1. Description
You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.
Return the minimum number of cameras needed to monitor all nodes of the tree.
2. Example
Example 1:
Input: root = [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.
Example 2:
Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.
3. Constraints
- The number of nodes in the tree is in the range [1, 1000].
- Node.val == 0
4. Solutions
Depth-First Search
n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
int minCameraCover(TreeNode *root) {
if (find_cover_(root) == 2) {
++result_;
}
return result_;
}
private:
int result_ = 0;
int find_cover_(TreeNode *root) {
// 0: there is a camera
// 1: there is no camera but the node has been covered
// 2: there is no camera and the node has not been covered
if (root == nullptr) {
// greedy, try to avoid the camera on the leaf node
// hard to explain null node return value, so use the status rather than dp array
return 1;
} else {
auto left = find_cover_(root->left);
auto right = find_cover_(root->right);
if (left == 2 || right == 2) {
++result_;
return 0;
} else if (left == 0 && right != 2 || left != 2 && right == 0) {
return 1;
} else {
return 2;
}
}
}
};