贪心算法解决监控二叉树问题

代码随想录链接:代码随想录

思路:

要想所装的监控数量最少，让叶子节点的父节点安摄像头。摄像头可以覆盖上中下三层，如果把摄像头放在叶子节点上，就浪费的一层的覆盖。所以把摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。

给每个节点定义三个状态:

0:表示该节点无覆盖，不在监控的范围内

1:表示该节点有监控

2:表示该节点在某个监控的覆盖范围内

对于空节点的处理:

为了让摄像头数量最少，我们要尽量让叶子节点的父节点安装摄像头，这样才能摄像头的数量最少。那么空节点不能是无覆盖的状态，这样叶子节点就要放摄像头了，空节点也不能是有摄像头的状态，这样叶子节点的父节点就没有必要放摄像头了，而是可以把摄像头放在叶子节点的爷爷节点上。所以空节点的状态只能是有覆盖(2)，这样就可以在叶子节点的父节点放摄像头了

流程:

定义一个全局变量count表示所安装摄像头的数量

采用递归版本的后序遍历方式遍历树的每个节点。如果该节点为空，返回2；如果该节点不为空，依次获取该节点的左子结点的状态和右子节点的状态。如果左子结点和右子节点都是有覆盖，那么该节点的状态为无覆盖，返回0；如果左子结点和右子节点有一个节点的状态为无覆盖(0)，那么令count++,同时在该节点处安装一个摄像头，返回1；如果左子结点和右子节点有一个节点安装摄像头(1),那么令该节点的状态为有覆盖，直接返回2

最后需要判断最上方的根节点的状态，如果根节点的状态为无覆盖，那么令count++

最后返回全部的监控数量count即可

代码:

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){
            //(2,2)
            return 0;
        }else if(left==0||right==0){
            // 左右节点都是无覆盖状态,那 根节点此时应该放一个摄像头
            // (0,0) (0,1) (0,2) (1,0) (2,0)
            // 状态值为 1 摄像头数 ++;
            res++;
            return 1;
        }else{
            // 左右节点的 状态为 (1,1) (1,2) (2,1) 也就是左右节点至少存在 1个摄像头，
            // 那么本节点就是处于被覆盖状态
            return 2;
        }
    }
}