968. 监控二叉树

描述

给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。

分析

道题和「打家劫舍III」很像，一样是二叉树。

• 每个结点只有三种状态：
  0：无法被观测
  1：可以被观测，但没摄像头
  2：可以被观测，有摄像头
• 由底向上便利，根据孩子的情况决定自己是哪种状态（依据是对于叶子节点，摄像头应当放置在父节点上，这样摄像头数量才少）
• 状态转移：

1. 两个孩子有一个是0：无法被观测，则当前结点必须是2：可以被观测，有摄像头
2. 两个孩子有一个是2：可以被观测，有摄像头，则当前结点应当是1：可以被观测，但没摄像头
3. 两个孩子都是1：可以被观测，但没摄像头，则当前几点应当是0：无法被观测
   三个状态转移的优先级：1>2>3。

为什么对于叶子节点，摄像头应当放置在父节点上？
理由是：每个结点都与可以被观测或者本身有摄像头，那么对于叶子节点来说，想要监控叶子节点，有两种选择，1.监控放在叶子节点，2.监控放在叶子节点的父节点。叶子节点的父节点的数量小于等于叶子节点的数量，所以选择第二种方案。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res = 0;
    public int minCameraCover(TreeNode root) {
        if(solve(root) == 0){
            res++;
        }
        return res;
    }

    public int solve(TreeNode root){
        if(root == null){
            return 1;
        }
        int a = solve(root.left);
        int b = solve(root.right);
        if(a == 0 || b == 0){
            res++;
            return 2;
        }
        if(a == 2 || b == 2){
            return 1;
        }
        return 0;
    }
}