22.监控二叉树

题目描述

给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视 其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。

解题思路

递归

约定如果某棵树的所有节点都被监控，则称该树被[覆盖]。

假设当前节点为root，其左右孩子为left，right。如果要覆盖以root为根的树，有两种情况：

• 若在root处安放摄像头，则孩子left，right一定也会被监控到。此时，只需要保证left的两棵子树被覆盖，同时保证right的两棵子树也被覆盖。
• 如果root不安放摄像头，则除了覆盖root的两棵子树以外，孩子left，right之一必须要安装摄像头，从而保证root被监控到。

因此，对于每个节点root，需要维护三种类型的状态：

• a：root必须放置摄像头的情况下，覆盖整棵树需要的摄像头数目。
• b：覆盖整棵树需要的摄像头数目，无论root是否放置摄像头。
• c：覆盖两棵子树需要的摄像头数目，无论root本身是否被监控到。

根据定义可知，一定有a >= b >= c。

对于节点root，假设其左右孩子left，right对应的状态变量为（l_a,l_b,l_c）以及（r_a,r_b,r_c）。因此：

• a = l_c + r_c +1
• b = min(a,min(l_a + r_b,r_a + l_b))

对于c而言，要保证两棵子树被完全覆盖，要么root处放置一个摄像头，即a；要么root处不放摄像头，此时两棵子树分别保证自己被覆盖，需要的摄像头为l_b + r_b。

• c = min(a,l_b + r_b)

如果root的孩子为null，则该孩子对应的变量a返回一个大整数，用于标识不可能的情形。

最终，根节点的状态变量b即为要求出的答案

Code：

class Solution{
    public int minCameraCover(TreeNode root){
        int[] array = dfs(root);
        return array[1];
    }
    public int[] dfs(TreeNode root){
        if(root == null){
            return new int[]{Integer.MAX_VALUE / 2,0,0};
        }
        int[] leftArray = dfs(root.left);
        int[] rightArray = dfs(root.right);
        int[] array = new int[3];
        array[0] = leftArray[2] + rightArray[2] + 1;
        array[1] = Math.min(array[0],Math.min(leftArray[0] + rightArray[1],leftArray[1] + rightArray[0]));
        array[2] = Math.min(array[0],leftArray[1] + rightArray[1]);
        return array;
    }
}