Binary Tree Cameras Hard 0 attempts
LeetCode ↗

Binary Tree Cameras

Hard TreeBinary TreeDFS LeetCode

Given a binary tree, install cameras on nodes so that every node is monitored. A camera at a node monitors its parent, itself, and children. Return the minimum number of cameras needed.

Example: root = [0,0,null,0,0] → Output: 1

Sample Input
—
Sample Output
—
Constraints
  • 1 <= number of nodes <= 1000
  • Node.val == 0
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.

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