968. Binary Tree Cameras

Version #1 Greedy DFS
这个题最开始想到了一定不是在leaf上放 cam,因为这样效率是最低的
错在没有想到所有的node是有三种状态的
// 0-> not monitored, 1-> monitored without cam, 2-> monitored with a cam
如果用这三种情况表示，思路就非常straight forward了
假如left or right有任意的没有 monitored的点，那么它们必须被当前点cover，当前点必须是2
如果它们都被cover了且任意一个点有cam，那么可以cover当前点，当前点就是1
如果左右孩子都被cover了但是都没有cam，那么当前点是0，等待着被它的parent cover


[0,0,null,null,0,0,null,null,0,0]
[0]


97.50 %
class Solution {
    private int count;
    // 0-> not monitored, 1-> monitored without cam, 2-> monitored with a cam
    public int minCameraCover(TreeNode root) {
        if (dfs(root) == 0) count++;
        return count;
    }
   
    private int dfs(TreeNode node) {
        if (node.left == null && node.right == null) return 0; // we don't put cam on leaf
        int left = node.left == null ? 1 : dfs(node.left);
        int right = node.right == null ? 1 : dfs(node.right);
        if (left == 0 || right == 0) {
            count++;
            return 2;
        } else if (left == 2 || right == 2) {
            return 1;
        } else {
            return 0;
        }
    }
}