题目
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1：
输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。示例 2：
输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。提示：
- 给定树的节点数的范围是
[1, 1000]。 - 每个节点的值都是 0。
解答
- 贪心算法
本题是一道贪心算法的题目。通过对题目进行分析，我们可以发现有以下几种情况：
1.如果一个节点没有被监控，那么它必须要安装一个摄像头。
2.如果一个节点安装了摄像头，那么它的父节点就可以被监控了。
3.如果一个节点的子节点被监控了，那么这个节点也可以被监控。
因此，我们可以采用自下而上的方式进行处理，从叶子节点开始向根节点进行处理。对于每个节点，我们可以有三种状态：
0：该节点没有装摄像头，且它的子节点中也没有装摄像头的节点，此时应该给他装一个摄像头。
1：该节点没有装摄像头，但是它的子节点中至少有一个装摄像头的节点，此时应该给他的父节点装一个摄像头。
2：该节点装摄像头了，因此它无需再安装一个摄像头。
对于每个节点，我们可以采用递归的方式进行处理。当节点为叶子节点时，它的状态为0。对于其他节点，如果它的子节点中存在状态为0的节点，那么该节点的状态为1，表示需要安装摄像头。如果它的子节点中都存在状态为1或2的节点，那么该节点的状态为0，表示不需要安装摄像头，但是它的父节点需要安装摄像头。如果它的子节点中存在状态为2的节点，那么该节点的状态为1，表示不需要安装摄像头，因为它的子节点已经可以覆盖它了。
最后，根据根节点的状态来判断是否需要安装摄像头。如果根节点的状态为0或1，那么需要安装一个摄像头。如果根节点的状态为2，那么不需要安装摄像头。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int minCameraCover(TreeNode* root) {
int res = 0;
if (dfs(root, res) == 0) { // 根节点未被监控
res++;
}
return res;
}
int dfs(TreeNode* node, int& res) {
if (node == nullptr) {
return 2; // 空节点不需要监控，返回2
}
int left = dfs(node->left, res);
int right = dfs(node->right, res);
if (left == 0 || right == 0) { // 左右子节点有未被监控的节点，该节点需要安装摄像头
res++; // 安装了摄像头
return 1; // return 1是指该节点没有被监控，但是它的子节点中至少有一个被监控的节点。
} else if (left == 1 || right == 1) { // 左右子节点中至少有一个节点被监控
return 2; // return 2是指该节点被监控了。
} else { // 左右子节点均被监控
return 0; // return 0是指该节点没有装摄像头
}
}
};其中，dfs函数的返回值为当前节点的状态。如果返回值为0，表示当前节点需要安装摄像头；如果返回值为1，表示当前节点不需要安装摄像头，但是它的父节点需要安装摄像头；如果返回值为2，表示当前节点不需要安装摄像头。res为引用类型，表示安装摄像头的数量。