Grokking 207

class Solution {

  Set<TreeNode> covered;
  int numCameras = 0;
  public int minCameraCover(TreeNode root) {
    covered = new HashSet<>();
    numCameras = 0;

    // null node is always covered
    covered.add(null);

    getCover(root, null);

    // if root node is not covered, add a camera at root node
    if (!covered.contains(root)) {
      numCameras++;
    }

    return numCameras;
  }

  public void getCover(TreeNode node, TreeNode parent) {
    if (node != null) {
      getCover(node.left, node);
      getCover(node.right, node);

      if (parent == null && !covered.contains(node) ||
          !covered.contains(node.left) ||
          !covered.contains(node.right)) {
        // add a camera to current node
        numCameras++;

        // update covered nodes
        covered.add(node);
        covered.add(parent);
        covered.add(node.left);
        covered.add(node.right);
      }
    }
  }
}