贪心算法---监控二叉树

题目：

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

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

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

思路：

叶结点上不能放摄像头，在叶结点的父亲节点上开始放摄像头。故使用后序遍历，从二叉树底部向上依次设置节点的状态。0表示无覆盖，1表示有摄像头，2表示有覆盖。

空节点的状态不能是无覆盖，又不能放摄像头，因此空姐点的状态为有覆盖。

递归的终止条件应该是遇到空节点，返回2（有覆盖）。

单层递归逻辑只需根据节点的左右孩子情况来设置节点的状态，保证两个孩子都能被监控。

情况有四种：

1.左右节点都有覆盖，则节点状态为无覆盖

2.左右节点至少一个为无覆盖，则节点状态为有摄像头

3.左右节点至少一个为有摄像头，则节点状态为有覆盖

4.头节点状态为无覆盖时，应在头节点位置放摄像头

代码：

    int camera=0;//记录摄像头数量
    public int minCameraCover(TreeNode root) {
        //情况四：头节点没有覆盖,在头结点上放一个摄像头
        if(minCamera(root)==0){
            camera++;
        }
        return camera;

    }
    //节点状态：0为无覆盖，1为有摄像头，2为有覆盖
    //后序遍历从底部向上设置状态，只需考虑左右孩子状态来设置中间节点状态，使左右孩子都被监控到
    public int minCamera(TreeNode root){
        //空节点默认为有覆盖状态，避免在叶子节点上放摄像头
        if(root==null){
            return 2;
        }
        int left=minCamera(root.left);
        int right=minCamera(root.right);
        //情况一：左右节点都有覆盖，中间节点状态应为无覆盖
        //(2,2)
        if(left==2&&right==2) return 0;
        //情况二：左右节点至少一个无覆盖，中间节点状态应为有摄像头
        //(0,0)(0,1)(1,0)(0,2)(2,0)
        else if(left==0||right==0) {
            camera++;
            return 1;
        }
        //情况三：左右节点至少有一个摄像头，中间节点状态应为有覆盖
        //(1,1)(1,2)(2,1)
        else return 2;
    }