题目

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

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

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

二叉树递归套路

以x为头的树,返回值有3中情况:
1) x上面无相机,但是x是被覆盖的,而且x底下所有节点都被覆盖了在这种情况下,请问需要几个相机
2) x上面有相机,x是被覆盖的,而且x底下所有节点都被覆盖了在这种情况下,请问需要几个相机
3) x既无相机,也没被覆盖,x底下所有节点都被覆盖了在这种情况下,请问需要几个相机

二叉树递归套路是说,如果我们想以x为头的整棵树都被覆盖了,需要哪些可能性?
那就两种可能性。第1种可能性就是x上面有相机,但是它被覆盖了。
第2种可能就是x上面无相机,但它被覆盖了
会少一种可能性,这种情况下你的这个两种可能性是不够的,收集信息的时候,我确实需要我的左树告诉我,它没被覆盖,但它底下都被覆盖的相机数量,因为我这儿放一个相机是可以补救他们的

二叉树的递归套路意义是什么?
意义就在于,他起码能够给你一个最初始的想法,你去分析答案的过程中。你肯定是要画与指数之间的拓扑关系去分析答案的,如果你发现你的可能性不够,你就往里加信息

为啥我要求x下方都被覆盖?很显而易见。因为x如果没被覆盖,它至少有它的父能补救他。但如果x下方的点没被覆盖,你往上返回爷爷辈的节点就再也无法补救,没有被覆盖的节点了

    public static class TreeNode {
        public int value;
        public TreeNode left;
        public TreeNode right;
    }

    public static int minCameraCover1(TreeNode root) {
        Info data = process1(root);
        return (int) Math.min(data.uncovered + 1, Math.min(data.coveredNoCamera, data.coveredHasCamera));
    }

    // 潜台词：x是头节点，x下方的点都被覆盖的情况下
    public static class Info {
        public long uncovered; // x没有被覆盖，x为头的树至少需要几个相机
        public long coveredNoCamera; // x被相机覆盖，但是x没相机，x为头的树至少需要几个相机
        public long coveredHasCamera; // x被相机覆盖了，并且x上放了相机，x为头的树至少需要几个相机

        public Info(long un, long no, long has) {
            uncovered = un;
            coveredNoCamera = no;
            coveredHasCamera = has;
        }
    }

    // 所有可能性都穷尽了
    public static Info process1(TreeNode X) {
        if (X == null) { // base case
            return new Info(Integer.MAX_VALUE, 0, Integer.MAX_VALUE);
        }

        Info left = process1(X.left);
        Info right = process1(X.right);
        // x uncovered x自己不被覆盖，x下方所有节点，都被覆盖
        // 左孩子： 左孩子没被覆盖，左孩子以下的点都被覆盖
        // 左孩子被覆盖但没相机，左孩子以下的点都被覆盖
        // 左孩子被覆盖也有相机，左孩子以下的点都被覆盖
        long uncovered = left.coveredNoCamera + right.coveredNoCamera;

        // x下方的点都被covered，x也被cover，但x上没相机
        long coveredNoCamera = Math.min(
                // 1)
                left.coveredHasCamera + right.coveredHasCamera,
                Math.min(// 2)
                        left.coveredHasCamera + right.coveredNoCamera,
                        // 3)
                        left.coveredNoCamera + right.coveredHasCamera));
        // x下方的点都被covered，x也被cover，且x上有相机
        long coveredHasCamera = 
                Math.min(left.uncovered, Math.min(left.coveredNoCamera, left.coveredHasCamera))
                + Math.min(right.uncovered, Math.min(right.coveredNoCamera, right.coveredHasCamera))
                + 1;
        return new Info(uncovered, coveredNoCamera, coveredHasCamera);
    }

优化

对于空树
只有一种解,被覆盖了没相机
所以面对这种最简单的情况,我们其实就是不放相机,恐怕后续的解会最优
因此我们只需给父节点返回一种信息就够了

当左树和右树只返回一种结果给父节点,那么父节点也只用返回一种信息给爷爷节点

我们需要记录节点的状态,有3种
1)没被覆盖
2)被覆盖了有相机
3)被覆盖了没有相机

可能性分析
1)左树或者右树有一个没被覆盖的,父节点只能放相机
2)左树或者右树都被覆盖,且有一棵树有相机,父节点会被子树的相机覆盖,因此不放相机
3)左树或者右树都被覆盖,且都没放相机,父节点返回没被覆盖,留给爷爷节点放相机

代码

    public static int minCameraCover2(TreeNode root) {
        Data data = process2(root);
        return data.cameras + (data.status == Status.UNCOVERED ? 1 : 0);
    }

    // 以x为头，x下方的节点都是被covered，x自己的状况，分三种
    public static enum Status {
        UNCOVERED, COVERED_NO_CAMERA, COVERED_HAS_CAMERA
    }

    // 以x为头，x下方的节点都是被covered，得到的最优解中：
    // x是什么状态，在这种状态下，需要至少几个相机
    public static class Data {
        public Status status;
        public int cameras;

        public Data(Status status, int cameras) {
            this.status = status;
            this.cameras = cameras;
        }
    }

    public static Data process2(TreeNode X) {
        if (X == null) {
            return new Data(Status.COVERED_NO_CAMERA, 0);
        }
        Data left = process2(X.left);
        Data right = process2(X.right);
        int cameras = left.cameras + right.cameras;
        
        // 左、或右，哪怕有一个没覆盖
        if (left.status == Status.UNCOVERED || right.status == Status.UNCOVERED) {
            return new Data(Status.COVERED_HAS_CAMERA, cameras + 1);
        }

        // 左右孩子，不存在没被覆盖的情况
        if (left.status == Status.COVERED_HAS_CAMERA || right.status == Status.COVERED_HAS_CAMERA) {
            return new Data(Status.COVERED_NO_CAMERA, cameras);
        }
        // 左右孩子，不存在没被覆盖的情况，也都没有相机
        return new Data(Status.UNCOVERED, cameras);
    }