监控二叉树

968. 监控二叉树

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

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

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

示例 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 {
    private int ans = 0;
    public int minCameraCover(TreeNode root) {
        if(root == null){
            return ans;
        }
        //只有一个结点，为当前结点安装相机
        if(dfs(root) == 0){
            ++ans;
        }
        return ans;
    }   

    // 0: 待覆盖; 1: 已覆盖; 2: 已安装相机
    public int dfs(TreeNode root){
        //结点为空表示已覆盖
        if(root == null){
            return 1;
        }
        int l = dfs(root.left);
        int r = dfs(root.right);

        if(l == 0 || r == 0){ // 有任意一个子结点未覆盖就需要将当前结点安装相机
            ans += 1;
            return 2;
        }else if(l == 2 || r == 2){ // 任意一个结点安装了相机，当前结点为已覆盖
            return 1;
        }else{
            return 0; //子结点都已覆盖，且都没有相机，当前结点由父节点来覆盖
        }
    }
}