贪心
/**
* 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++