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.
Constraints
The number of nodes in the given tree will be in the range [1, 1000].
Every node has value 0.
Approach
Links
GeeksforGeeks
Leetcode
ProgramCreek
YouTube
Examples
Input: [0, 0, null, 0, 0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.
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.
Solutions
// 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;
}
}
/**
* Time complexity :
* Space complexity :
*/
class Solution {
private int count = 0;
public int minCameraCover(TreeNode root) {
return dfs(root) > 2? count + 1: count;
}
private int dfs(TreeNode node) {
if(node == null) {
return 0;
}
int val = dfs(node.left) + dfs(node.right);
if(val == 0) {
return 3;
}
if(val < 3) {
return 0;
}
count++;
return 1;
}
}
