968. 监控二叉树 (opens new window)

1.深搜+状态机+贪心

弄明白问题的出发点，也就是什么样的节点一定需要放置摄像头？然后再从这个起始状态出发进行递推

核心：找到叶子节点的父节点，然后放置摄像头(确保叶子节点被监控)。递归时根据子节点的状态，自底向上放置摄像头。另外基于贪心策略，如果子节点没有被监控，那么可以选择在父节点放摄像头。

每个节点根据子节点的状态来判决是否放置摄像头：

• 返回0：表示当前节点为叶子节点
• 返回1：表示当前节点上未放置摄像头，但是已经被监控(子节点放置了摄像头)
• 返回2：表示当前节点上放置摄像头

放置摄像头只有两种情况，也就是子节点没有被监控到：

• 子节点至少出现一个状态0
• 子节点没有放置摄像头，且子节点的子节点也没有放置摄像头，那么当前需要放置。比如【空，放，空，空，放，空】中的第二个节点放置了摄像头(第三个节点不需要放置摄像头)。

class Solution {
    int res=0;
    public int minCameraCover(TreeNode root) {
        int ans=dfs(root);
        if(ans==0) res++;
        return res;
    }
    //返回0表示当前节点为叶子节点
    //返回1表示当前节点上未放置摄像头，但是已经被监控
    //返回2表示当前节点上放置摄像头
    public int dfs(TreeNode root){
        if(root.left==null&&root.right==null) return 0;
        int leftres=root.left==null?-1:dfs(root.left);
        int rightres=root.right==null?-1:dfs(root.right);
        if(leftres==0||rightres==0){
            res++;
            return 2;
        }
        else if(leftres==2||rightres==2) return 1;
        else{
            //当前节点不需要放置摄像头，在父节点放
            return 0;
        }
    }
}