监控二叉树

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

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

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

示例

输入：[0,0,null,0,0]

输出：1

解释：如图所示，一台摄像头足以监控所有节点。

思路

如何放置才能使放置的摄像头最少呢？首先肯定不能从头节点或者叶子节点开始放置，因为一个摄像头可以监视三层节点，如果从头节点或者叶子节点开始放置会造成浪费。那么是从下往上还是从上往下呢？应该是从下往上，如果从上往下也就省下了头节点一个摄像头，从下往上有许多叶子节点，可以省下很多摄像头。

总结来说就是在叶子节点的父节点放置摄像头，然后从下往上放置摄像头，直到头节点，这样放置的摄像头最少。

每个节点是否放置摄像头都需要根据子节点的状态来确定，每个节点都可以有三种状态：

• 未被覆盖
• 有摄像头
• 已被覆盖

如何根据子节点状态来确定节点状态呢？有以下四种情况：

1. 左右两子节点都已被覆盖

   子节点都已经被覆盖了，自己没必要成为摄像头，而是请求上层成为摄像头来覆盖自己，所以为无覆盖状态

2. 左右节点至少一个为无覆盖

   子节点有无覆盖的，自己肯定要成为摄像头来覆盖它，所以为有摄像头状态

3. 左右节点至少一个为有摄像头

   子节点为有摄像头能监视自己，所以为有覆盖状态

4. 头节点为无覆盖状态

   最后可能会出现头节点为无覆盖状态，那么只有让头节点成为摄像头监视自己了

因为是从下往上，每个节点状态根据子节点状态确定，所以使用后序遍历的遍历顺序，用0、1、2来代表节点的三种状态，用cameraNum来记录摄像头数，每次确定节点状态为1即有摄像头时就将摄像头数加1。

与图中不同，在实现的时候我们不需要更新子节点的状态。还有，递归终止条件也就是空节点的状态是什么呢，因为叶子节点应该是无覆盖，那么空节点的状态就应该是已覆盖了。

实现代码

class Solution {
    private int cameraNum=0;
    public int minCameraCover(TreeNode root) {
        int rootStatus=traversal(root);
        if(rootStatus==0)
            cameraNum++;
        return cameraNum;
    }

    //0：未覆盖
    //1：有摄像头
    //2：有覆盖
    public int traversal(TreeNode node) {
        if(node==null)
            return 2;
        int leftStatus = traversal(node.left);
        int rightStatus = traversal(node.right);
        //如果左右两节点为有覆盖，则此节点为未覆盖
        if(leftStatus==2&&rightStatus==2)
            return 0;
        //如果两节点中至少一个未覆盖，则此节点应该为有摄像头
        if(leftStatus==0||rightStatus==0) {
            cameraNum++;
            return 1;
        }
        //如果两节点至少有一个摄像头，则此节点为有覆盖
        //if(leftStatus==2||rightStatus==2)
        //    return 2;
        return 2;
    }
}