贪心算法，二叉树与贪心的结合，有点难...... LeetCode:968.监督

这题好难！（注释版，谢谢Carl，讲的很清晰！

class Solution {

public:

    int result = 0;

    // 0：无覆盖， 1：有摄像头，2：有覆盖

    int inordered(TreeNode* cur) {

        if (!cur) return 2; // null节点表示有覆盖， 为的是让叶子节点的父节点有摄像头

        int left = inordered(cur->left);

        int right = inordered(cur->right);

        // 1.如果左节点和右节点都有覆盖，则父节点设为无覆盖，这样父节点的父节点可以设为有摄像头

        if (left == 2 && right == 2) return 0;

        // 2.如果左右节点至少有一个为无覆盖，则父节点设置为有摄像头

        if (left == 0 || right == 0) {

            result++;

            return 1;

        }

        // 3.如果左右节点至少有一个为有摄像头，则父节点设置为有覆盖（注意：必须先写条件2，再写条件3 -> 可化一棵树模拟！

        if (left == 1 || right == 1) return 2;

        return -1; // 保证编译正常，不会运行到这一步

    }

    int minCameraCover(TreeNode* root) {

        if (inordered(root) == 0) result++; // 4. 根节点无覆盖时，摄像头+1

        return result;

    }

};