Back to DSA

Binary Tree Cameras

hard
Acceptance: 38%
Binary Tree

Place surveillance cameras on the nodes of a binary tree so that every node is observed. A camera on a node covers that node, its parent, and its direct children. Determine the smallest number of cameras required to cover every node in the tree.

Examples

Example 1:
Input:root = [0,0,null,0,null,0,0]
Output:2
Example 2:
Input:root = [0,0,0]
Output:1

Hints

Related Problems

Maximum Depth of Binary TreeeasyInvert Binary TreeeasyValidate Binary Search TreemediumLowest Common Ancestor of a Binary TreemediumBinary Tree Level Order Traversalmedium
00:00
class Solution {
    private int cameras = 0;

    public int minCameraCover(TreeNode root) {
        if (dfs(root) == 0) cameras++;
        return cameras;
    }

    // 0 = not covered, 1 = has camera, 2 = covered
    private int dfs(TreeNode node) {
        if (node == null) return 2;
        int left = dfs(node.left);
        int right = dfs(node.right);
        if (left == 0 || right == 0) {
            cameras++;
            return 1;
        }
        if (left == 1 || right == 1) return 2;
        return 0;
    }
}
Time complexityO(n)
Space complexityO(h)