day31

968监控二叉树
class Solution {
private:
    int result = 0;
    int traversal(TreeNode* cur){
        //递归出口
        if(cur == NULL) return 2;
        //左
int left = traversal(cur->left);
        //右
int right = traversal(cur->right);
        //中
        //情况1
        if(left == 2 && right == 2) return 0;
        //情况2
        if(left == 0 || right == 0){
            result++;
            return 1;
        }
        //情况3
        if(left == 1 || right == 1) return 2;
        return -1;//其实上面三种情况包括了所有情况，并不会走到这步，但必须这里加个return，否则编译不通过
    }
public:
    int minCameraCover(TreeNode* root) {
        //贪心和二叉树的结合，尽量让叶子节点的根节点安装摄像头，可以覆盖上中下三层，减少覆盖范围的浪费
        //后序遍历这个二叉树，根据叶子结点的状态（0无覆盖、1有摄像头、2有覆盖），来判断根节点的状态
        //注意，遇到空结点的时候，将其状态定为2有覆盖，才能让叶子节点是个0无覆盖状态，而其父节点为1有摄像头
        //根据叶子结点的情况主要可以分为以下三类
        //1、左右叶子节点都为2有覆盖，则父节点为0无覆盖(等着它的上层加摄像头来覆盖)
        //2、左右结点至少有一个为0无覆盖，则父节点必须为1有摄像头
        //3、左右结点至少有一个为1有摄像头，则父节点必须为2有覆盖（注意，情况2的判断必须要放在3之前）
        //此外，还有一种特殊情况
        //4、根节点最后为0无覆盖，因为根节点没有父节点，所以被办法对其进行上层加摄像头覆盖了，所以此时根节点要放一个摄像头
        if(traversal(root) == 0) result++;//特殊情况4出现，摄像头再加一个
        return result;
    }
};