【玩转贪心算法专题】968. 监控二叉树【困难】
1、力扣链接
https://leetcode.cn/problems/binary-tree-cameras/description/
2、题目描述
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1：
输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。
示例 2：
输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
提示：
给定树的节点数的范围是 [1, 1000]。
每个节点的值都是 0。
3、题目分析
对于贪心算法的题目，可从 寻求局部最优解入手，以局部最优解，得到全局最优解
本题思路：
遍历二叉树，最终题目要求需返回摄像头的个数，所以共分为几种情况
有如下三种：
该节点无覆盖
本节点有摄像头
本节点有覆盖
我们分别有三个数字来表示：
0：该节点无覆盖
1：本节点有摄像头
2：本节点有覆盖
主要有如下四类情况：
情况1：左右节点都有覆盖
左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。
情况2：左右节点至少有一个无覆盖的情况
父节点就应该放摄像头。
此时摄像头的数量要加一，并且return 1，代表中间节点放摄像头。
情况3：左右节点至少有一个有摄像头
如果是以下情况，其实就是 左右孩子节点有一个有摄像头了，那么其父节点就应该是2
情况4：头结点没有覆盖
在递归结束之后，还要判断根节点，如果没有覆盖，result++
4、代码实现
1、Java
/*** 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) {//对根节点的状态去做校验，防止根节点是无覆盖的状态if(minCame(root) == 0){res++;}return res;}/**节点的状态值：0 表示无覆盖1 表示 有摄像头2 表示有覆盖后序遍历 根据左右节点的情况，来判读 自己的状态*/public int minCame(TreeNode root){if(root == null){// 空节点默认为 有覆盖状态 避免在叶子节点上放摄像头return 2;}int left = minCame(root.left);int right = minCame(root.right);//如果左右节点都覆盖了的话，那么本节点一定没有被覆盖，没有摄像头if(left==2&&right==2){return 0;}if(left==0||right==0){//左右节点至少有一个是无覆盖状态，那 根节点此时应该放一个摄像头//（0，0）（0,1）(0,2) (1,0) (2,0)res++;return 1;}else{//左右节点的 状态为 （1，1） （1，2）（2，1）也就是左右节点至少存在 1个 摄像头//那么本节点就算处于被覆盖状态return 2;}}
}
2、C++
class Solution {
private:int result;int traversal(TreeNode* cur) {if (cur == NULL) return 2;int left = traversal(cur->left); // 左int right = traversal(cur->right); // 右if (left == 2 && right == 2) return 0;else if (left == 0 || right == 0) {result++;return 1;} else return 2;}
public:int minCameraCover(TreeNode* root) {result = 0;if (traversal(root) == 0) { // root 无覆盖result++;}return result;}
};3、python
class Solution:# Greedy Algo:# 从下往上安装摄像头：跳过leaves这样安装数量最少，局部最优 -> 全局最优# 先给leaves的父节点安装，然后每隔两层节点安装一个摄像头，直到Head# 0: 该节点未覆盖# 1: 该节点有摄像头# 2: 该节点有覆盖def minCameraCover(self, root: TreeNode) -> int:# 定义递归函数result = [0] # 用于记录摄像头的安装数量if self.traversal(root, result) == 0:result[0] += 1return result[0]def traversal(self, cur: TreeNode, result: List[int]) -> int:if not cur:return 2left = self.traversal(cur.left, result)right = self.traversal(cur.right, result)# 情况1: 左右节点都有覆盖if left == 2 and right == 2:return 0# 情况2:# left == 0 && right == 0 左右节点无覆盖# left == 1 && right == 0 左节点有摄像头，右节点无覆盖# left == 0 && right == 1 左节点无覆盖，右节点有摄像头# left == 0 && right == 2 左节点无覆盖，右节点覆盖# left == 2 && right == 0 左节点覆盖，右节点无覆盖elif left == 0 or right == 0:result[0] += 1return 1# 情况3:# left == 1 && right == 2 左节点有摄像头，右节点有覆盖# left == 2 && right == 1 左节点有覆盖，右节点有摄像头# left == 1 && right == 1 左右节点都有摄像头else:return 24、go
const inf = math.MaxInt64 / 2func minCameraCover(root *TreeNode) int {var dfs func(*TreeNode) (a, b, c int)dfs = func(node *TreeNode) (a, b, c int) {if node == nil {return inf, 0, 0}lefta, leftb, leftc := dfs(node.Left)righta, rightb, rightc := dfs(node.Right)a = leftc + rightc + 1b = min(a, min(lefta+rightb, righta+leftb))c = min(a, leftb+rightb)return}_, ans, _ := dfs(root)return ans
}func min(a, b int) int {if a <= b {return a}return b
}
