leetcode-968：监控二叉树

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

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

class Solution {
public:
    int res;
    int traversal(TreeNode* cur){
        if(cur==nullptr) return 2;
        int left=traversal(cur->left);
        int right=traversal(cur->right);
        if(left==2&&right==2) return 0;//左右节点都有覆盖，那么让该节点无摄像头
        if(left==0||right==0){  //如果左右节点有一个无覆盖，就要让该节点放摄像头
            res++;
            return 1;
        }
        if(left==1||right==1) return 2; //如果有有一个有摄像头，那么该节点表示覆盖
        return -1;//不会到达这一步
    }
    int minCameraCover(TreeNode* root) {
        res=0;
        if(traversal(root)==0) res++;
        return res;
    }
};

// 版本二
class Solution {
private:
    int result;
    int traversal(TreeNode* cur) {
        if (cur == NULL) return 2;
        int left = traversal(cur->left);    // 左
        int right = traversal(cur->right);  // 右
        if (left == 2 && right == 2) return 0;
        else if (left == 0 || right == 0) {
            result++;
            return 1;
        } else return 2;
    }
public:
    int minCameraCover(TreeNode* root) {
        result = 0;
        if (traversal(root) == 0) { // root 无覆盖
            result++;
        }
        return result;
    }
};

enum STAT{
    Camera,
    Cover,
    NoCover
 };
class Solution {
public:
    int res;
    STAT dfs(TreeNode* cur){
        if(cur==nullptr) return Cover;
        STAT left=dfs(cur->left);
        STAT right=dfs(cur->right);
        if(left==Cover&&right==Cover) return NoCover;
        else if(left==NoCover||right==NoCover){
            res++;
            return Camera;
        }
        else return Cover;
    }
    int minCameraCover(TreeNode* root) {
        res=0;
        if(dfs(root)==NoCover) res++;
        return res;
    }
};