968. Binary Tree Cameras

Description

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

1. The number of nodes in the given tree will be in the range [1, 1000].

2. Every node has value 0.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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.

Solutions

TreeNode

// 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;
	}
}

Solution 1

/**
 * 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;
    }
}

Follow up