Binary Tree Cameras

Given a binary tree, we install cameras on the nodes of the tree. 

Each camera at a node can monitor its parent, itself, and its immediate children.

Calculate the minimum number of cameras needed to monitor all nodes of the tree.

 

Example 1:

Input: [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.

Example 2:

Input: [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.


Note:

  1. The number of nodes in the given tree will be in the range [1, 1000].
  2. Every node has value 0.

Solution:

/**
 * 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 {
    private int NOT_MONITORED = 0;
    private int MONITORED_NOCAM = 1;
    private int MONITORED_CAM = 2;
    
    public int minCameraCover(TreeNode root) {
        if (root == null) return 0;
        int[] count = new int[]{0};
        int top = helper(root, count);
        return count[0] + (top == NOT_MONITORED ? 1 : 0);
    }
    
    private int helper(TreeNode root, int[] count) {
        if (root == null) {
            return MONITORED_NOCAM;
        }
        int left = helper(root.left, count);
        int right = helper(root.right, count);
        if (left == NOT_MONITORED || right == NOT_MONITORED) {
            count[0] ++;
            return MONITORED_CAM;
        } else if (left == MONITORED_NOCAM && right == MONITORED_NOCAM) {
            return NOT_MONITORED;
        } else {
            return MONITORED_NOCAM;
        }
    }
}