题目描述

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

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

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

样例

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

示例 2：
输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 

算法1

当前节点为root,存在三种状态

状态一：root处放置摄像头，同时覆盖整棵树
状态二：root处可放置或不放置摄像头，同时覆盖整棵树
状态三：root处可能未被监控到，但root的左右子树被完全覆盖

root节点与左右子节点间的状态转移：

一： cur[0] = left[2] + right[2] + 1;
root处放置摄像头，数目+1，此时保证左右子节点被覆盖，
因此只需再保证左右子节点的左右子树被完全覆盖即可

二： cur[1] = Math.min(cur[0], Math.min(left[0] + right[1], right[0] + left[1]));
若root处不放置摄像头，则root的左子节点或右子节点需要放置摄像头，
从而覆盖root，选择两种方案中数目较小的方案

三： cur[2] = Math.min(cur[0], left[1] + right[1]);
保证root的左子树和右子树被完全覆盖

时间复杂度 $O(n)$

n为树中的节点数量，每个节点遍历一次

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minCameraCover(TreeNode root) {
        int[] res = dfs(root);
        return res[1];
    }
    public int[] dfs(TreeNode root){
        if(root == null) return new int[]{0x3f3f3f3f/2, 0, 0};
        int[] left = dfs(root.left);
        int[] right = dfs(root.right);
        int[] cur = new int[3];
        cur[0] = left[2] + right[2] + 1;
        cur[1] = Math.min(cur[0], Math.min(left[0] + right[1], right[0] + left[1]));
        cur[2] = Math.min(cur[0], left[1] + right[1]);
        return cur;
    }
}