Binary Tree Cameras Hard 0 attempts
LeetCode ↗

Binary Tree Cameras

Hard TreeBinary TreeDFS LeetCode

You're given the root of a binary tree and need to place security cameras on some of its nodes so that every node in the tree is watched. A camera placed on a node covers that node, its parent, and its direct children. Return the fewest cameras needed to cover the entire tree.

Input Format
Implement minCameraCover(root). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
root = [0,0,null,0,0]
Output
1

Example 2

Input
root = [0]
Output
1
Constraints
  • 1 <= number of nodes <= 1000
  • Node.val == 0
Test Cases (2)
Case 1
Args: [[0,0,null,0,0]] Expected: 1
Case 2
Args: [[0]] Expected: 1
Topics
TreeBinary TreeDFS

Greedy DFS (Bottom-Up)

Each node has 3 states: 0 = needs camera, 1 = has camera, 2 = covered. Greedily place cameras at parents of uncovered leaves.

javascript
function minCameraCover(root) {
  let cameras = 0;
  function dfs(node) {
    if (!node) return 2;
    const l = dfs(node.left), r = dfs(node.right);
    if (l === 0 || r === 0) { cameras++; return 1; }
    if (l === 1 || r === 1) return 2;
    return 0;
  }
  if (dfs(root) === 0) cameras++;
  return cameras;
}

Time: O(n) | Space: O(h)

Saved in this browser only. Private to you.

JavaScript