问题
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例
输入： [0,0,null,0,0]
输出： 1
解释： 如图所示，一台摄像头足以监控所有节点。
解答
class Solution {
public:
int minCameraCover(TreeNode* root) {
if (dfs(root) == 2) res++;
return res;
}
private:
int res = 0;
int dfs(TreeNode* root) { // 0: 监控 1: 被监控 2: 未被监控
if (!root) return 1;
int left = dfs(root->left);
int right = dfs(root->right);
if (left == 2 || right == 2) { // 存在子节点未被监控
res++;
return 0;
}
if (!left || !right) return 1; // 当前根节点已被监控
return 2;
}
};
重点思路
在递归途中，使用三种状态表示当前根结点：当前节点为监控，当前节点已被监控，当前节点尚未被监控。