968. Binary Tree Cameras.md

968. Binary Tree Cameras

Question:

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:

• Method 1: dfs + Greedy
  • I didn't get this question by myself.

  /**
   * Definition for a binary tree node.
   * public class TreeNode {
   *     int val;
   *     TreeNode left;
   *     TreeNode right;
   *     TreeNode(int x) { val = x; }
   * }
   */
  class Solution {
      private static final int NULL = 0;
      private static final int COVER = 1;
      private static final int CAMERA = 2;
      private int res;
      public int minCameraCover(TreeNode root) {
          if(dfs(root) == NULL) res++;
          return res;
      }
      private int dfs(TreeNode node){
          if(node == null) return COVER;
          int left = dfs(node.left);
          int right = dfs(node.right);
          if(left == NULL || right == NULL){
              res++;
              return CAMERA;
          }
          if(left == CAMERA || right == CAMERA) return COVER;
          return NULL;
      }
  }