贪心
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// 对摄像头计数
int res = 0;
public int minCameraCover(TreeNode root) {
// 4.根节点无覆盖
if(traversal(root) == 0){
res++;
}
return res;
}
// 后序遍历
public int traversal(TreeNode cur){
// 空节点返回状态2有覆盖
if(cur == null){
return 2;
}
// 左 处理逻辑
int left = traversal(cur.left);
// 右 处理逻辑
int right = traversal(cur.right);
// 中 处理逻辑
// 1.左右孩子都是有覆盖，则父节点为无覆盖
if(left == 2 && right == 2){
return 0;
}
// 2.左右孩子至少有一个无覆盖,父节点应该放一个摄像头
if(left == 0 || right == 0){
res++;
return 1;
}
// 3.左右孩子至少有一个有摄像头，父节点为有覆盖
if(left == 1 || right == 1){
return 2;
}
return 0;
}
}
题目解析：
- 情况1：左右节点都有覆盖
左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。
- 情况2：左右节点至少有一个无覆盖的情况
如果是以下情况，则中间节点（父节点）应该放摄像头：
left == 0 && right == 0 左右节点无覆盖
left == 1 && right == 0 左节点有摄像头，右节点无覆盖
left == 0 && right == 1 左节点有无覆盖，右节点摄像头
left == 0 && right == 2 左节点无覆盖，右节点覆盖
left == 2 && right == 0 左节点覆盖，右节点无覆盖
这个不难理解，毕竟有一个孩子没有覆盖，父节点就应该放摄像头。
此时摄像头的数量要加一，并且return 1，代表中间节点放摄像头。
- 情况3：左右节点至少有一个有摄像头
如果是以下情况，其实就是 左右孩子节点有一个有摄像头了，那么其父节点就应该是2（覆盖的状态）
left == 1 && right == 2 左节点有摄像头，右节点有覆盖
left == 2 && right == 1 左节点有覆盖，右节点有摄像头
left == 1 && right == 1 左右节点都有摄像头
- 情况4：头结点没有覆盖
以上都处理完了，递归结束之后，可能头结点 还有一个无覆盖的情况，所以递归结束之后，还要判断根节点，如果没有覆盖，result++
