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

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

Approach

Examples

Input: [0, 0, null, 0, 0]

Output: 1

Explanation: One camera is enough to monitor all nodes if placed as shown.

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

Follow up

Previous953. Verifying an Alien Dictionary Next970. Powerful Integers

Last updated 4 years ago

Was this helpful?