博客

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

示例 1：

输入：[0,0,null,0,0] 输出：1 解释：如图所示，一台摄像头足以监控所有节点。

• 本题使用贪心算法（遇事不决用贪心），从下往上进行搜索（从上往下后期要解决的节点数量过多），叶子节点的父节点作为摄像头所覆盖的区域是最多的，因此使用后序遍历，使用类似回溯的方式遍历整棵树并及时记录状态；

• 0表示未覆盖，1表示有摄像头，2表示已覆盖；

• 那空节点怎么办？标记为已覆盖（return），如果作为摄像头会影响叶子结点，如果作为未覆盖会使得叶子节点变成摄像头来覆盖空节点；

• 可能遇到的情况包括：子节点都覆盖，此节点作为上一个节点的叶子节点，标记为未覆盖即可；子节点只要有一个是未覆盖，父节点必须作为摄像头去覆盖；子节点有一个是摄像头，只需将此节点标记为已覆盖即可（不满足上一种情况的前提下）；

• 顺序不能乱，如果到最后还没有匹配，就返回-1，属于异常；

• 最后根节点未覆盖，就必须曾增加一个摄像头；

int res=0;
    public int minCameraCover(TreeNode root) {
        if(dfs(root)==0){//根节点未覆盖，摄像头加1
            res++;
        }
        return res;
    }
    int dfs(TreeNode root){
        if(root==null){
            return 2;//空节点记录为已覆盖，不影响叶子节点
        }
        int left=dfs(root.left);
        int right=dfs(root.right);
        if(left==2&&right==2){
            return 0;//左右节点都覆盖，此节点不装摄像头，标记为未覆盖，等待其父节点安装
        }
        if(left==0||right==0){//子节点只要有一个未覆盖，就需要安装摄像头
            res++;
            return 1;
        }
        if(left==1||right==1){//子节点只要有一个是摄像头，此节点都是已覆盖状态
            return 2;
        }
        return -1;//异常情况
    }