H968-监控二叉树

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

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

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

示例 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 {
public:
    //返回节点状态
    //0：该节点无覆盖
    //1：本节点有摄像头
    //2：本节点有覆盖
    int ans;
    int tra(TreeNode* root){
        if(root==nullptr) return 2; //空节点的上一个节点是有覆盖的,有覆盖之下空节点算有覆盖
        int left=tra(root->left);
        int right = tra(root->right);
        if(right==2&&left ==2) return 0;//节点两个子节点都被覆盖说明该节点无覆盖,通过上面的节点完成覆盖,这里从下往上遍历就不统计进去
        else if(left==0||right==0) { //两个节点都无覆盖,则应该添加摄像头记录了
            ans++;
            return 1;
        }
        else return 2;  //其他的一边只要有1就是有覆盖
    }

    int minCameraCover(TreeNode* root) {
        ans=0;
        int a= tra(root);
        if(a==0) ans++;
        return ans;
    }
};