【24届暑期实习】阿里云计算平台 DataWorks&PAI

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;    }};