Binary Tree Cameras

LeetCode Q 968 - Binary Tree Camerasl

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:

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

Solution: Greedy + Bottom-Up DFS

We greedily put cameras in the parent nodes to enlarging the monitoring range. There are 3 status of a parent node.

• If a parent has one un-monitored child, then we must put a camera in this parent.
• If a parent has two monitored but without camera children, then this parent is un-monitored.
• If a parent has two monitored children and one or more child has a camera, then this parent is monitored without camera.

Code:

private int NOT_MONITORED = 0;
private int MONITORED_NOCAM = 1;
private int MONITORED_WITHCAM = 2;
private int res = 0;

public int minCameraCover(TreeNode root) {
  return (dfs(root) == NOT_MONITORED ? 1 : 0) + res;
}

private int dfs(TreeNode root) {
  if (root == null) return MONITORED_NOCAM;

  int l = dfs(root.left);
  int r = dfs(root.right);

  if (l == NOT_MONITORED || r == NOT_MONITORED) {
    res++; return MONITORED_WITHCAM;
  } else if (l == MONITORED_NOCAM || r == MONITORED_NOCAM ) {
    return NOT_MONITORED;
  } else {
    return MONITORED_NOCAM;
  }
}