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. ```Java /**
    • 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; } } ```