968. 监控二叉树 - 力扣（LeetCode）

一、题目

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

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

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

示例 1：

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

示例 2：

输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。 

提示：

1. 给定树的节点数的范围是 [1, 1000]。
2. 每个节点的值都是 0。

二、代码

class Solution {
    // 潜台词：x是头节点，x下方的点都被覆盖的情况下
    public class Info {
        private long uncovered;
        private long coveredNoCamera;
        private long coveredHasCamera;

        public Info(long uncovered, long coveredNoCamera, long coveredHasCamera) {
            // x没有被覆盖（指的是没有被x下层的相机覆盖，上层有没有覆盖我们不管，此时的视角就认为x是根节点，他的上面已经没有节点了），x为头的树至少需要几个相机
            this.uncovered = uncovered;
            // x被相机覆盖，但是x没相机，x为头的树至少需要几个相机
            this.coveredNoCamera = coveredNoCamera;
            // x被相机覆盖了，并且x上放了相机，x为头的树至少需要几个相机
            this.coveredHasCamera = coveredHasCamera;
        }
    }


    public int minCameraCover(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Info rootInfo = process(root);
        // data.uncovered + 1既然你这个位置没有被覆盖，但是这个位置下面给都已经能保证被覆盖了，我干脆直接在这个位置给你一个相机就行了，所以这里要加1
        return (int) Math.min(rootInfo.uncovered + 1, Math.min(rootInfo.coveredNoCamera, rootInfo.coveredHasCamera));
    }

    // 将所有可能的情况都通过递归尝试出来
    public Info process(TreeNode head) {
        // 递归出口，当递归到最底层的空节点是，这个节点是必须被覆盖的，但是这个节点上不能放相机
        // 所以这里就返回被覆盖但是没相机的数量是0，其他的都是系统最大值，表示不存在这两种情况
        if (head == null) {
            return new Info(Integer.MAX_VALUE, 0, Integer.MAX_VALUE);
        }

        // 收集左树和右树的信息，然后再用收集上来的左树和右树的信息来得到当前这个节点的Info信息
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);

        // 计算x的uncovered
        // x节点没有被覆盖，但是x节点以下的节点全部都要被覆盖。如果x没有被覆盖，那么他的左右子节点上一定都没有相机，否则x就能被覆盖了
        long uncovered = leftInfo.coveredNoCamera + rightInfo.coveredNoCamera;

        // 计算x的coveredNoCamera
        // x下方的点都被covered，x也被cover，但x上没相机。这里我们不去考虑x的父节点，只考虑x下面的节点，所以满足这个情况，就说明x的左右子节点中至少存在一个节点是有相机的，否则x不可能被覆盖
        // 1、左子节点被覆盖有相机，右子节点被覆盖没有相机
        // 2、左子节点被覆盖没有相机，右子节点被覆盖有相机
        // 3、左子节点和右子节点都有相机
        long coveredNoCamera = Math.min(Math.min(leftInfo.coveredNoCamera + rightInfo.coveredHasCamera, rightInfo.coveredNoCamera + leftInfo.coveredHasCamera), leftInfo.coveredHasCamera + rightInfo.coveredHasCamera);

        // 计算x的coveredHasCamera
        // x下方的点都被covered，x也被cover，且x上有相机。这种情况下子节点三种可能性都可选，因为父节点有相机就能满足子节点的任何情况，就算是子节点没被下层相机覆盖，父节点的相机也可以将其覆盖掉，保证满足要求。就将左右子树所有可能的情况都罗列出来取最小值相加，最后还要再加1，把x节点的相机也算进去。
        long coveredHasCamera = Math.min(leftInfo.uncovered, Math.min(leftInfo.coveredNoCamera, leftInfo.coveredHasCamera))
            + Math.min(rightInfo.uncovered, Math.min(rightInfo.coveredNoCamera, rightInfo.coveredHasCamera))
            + 1;

        return new Info(uncovered, coveredNoCamera, coveredHasCamera);
    }
}

三、解题思路 

通过二叉树递归，收集左右子树的信息，然后利用左右子树的信息得到父节点的信息。将所有的情况都罗列出来，向上返回即可得到最终的答案。