Binary Tree Cameras
Minimum cameras to monitor all nodes — greedy bottom-up with three states (covered, has camera, uncovered).
Problem#
A camera at a node covers itself and its parent and children. Return the minimum number of cameras needed to cover all nodes.
Examples#
[0,0,null,0,0]→1
Constraints#
1 <= n <= 1000.
Approach#
DFS returning a state: 0 = needs coverage, 1 = covered (by child), 2 = has camera. If any child returns 0, this node must hold a camera (count++, return 2). If any child returns 2, this node is already covered (return 1). Else 0 (covered by neither side; parent must cover us).
Solution#
class Solution {public: int minCameraCover(TreeNode* root) { int cameras = 0; function<int(TreeNode*)> dfs = [&](TreeNode* n) -> int { if (!n) return 1; // null counts as covered int l = dfs(n->left), r = dfs(n->right); if (l == 0 || r == 0) { ++cameras; return 2; } if (l == 2 || r == 2) return 1; return 0; }; if (dfs(root) == 0) ++cameras; return cameras; }};func minCameraCover(root *TreeNode) int { cameras := 0 var dfs func(*TreeNode) int dfs = func(n *TreeNode) int { if n == nil { return 1 } l := dfs(n.Left) r := dfs(n.Right) if l == 0 || r == 0 { cameras++ return 2 } if l == 2 || r == 2 { return 1 } return 0 } if dfs(root) == 0 { cameras++ } return cameras}from typing import Optional
class Solution: def minCameraCover(self, root: Optional[TreeNode]) -> int: self.cameras = 0
def dfs(n: Optional[TreeNode]) -> int: if not n: return 1 # null counts as covered l = dfs(n.left) r = dfs(n.right) if l == 0 or r == 0: self.cameras += 1 return 2 if l == 2 or r == 2: return 1 return 0
if dfs(root) == 0: self.cameras += 1 return self.camerasvar minCameraCover = function(root) { let cameras = 0; const dfs = (n) => { if (!n) return 1; // null counts as covered const l = dfs(n.left), r = dfs(n.right); if (l === 0 || r === 0) { cameras++; return 2; } if (l === 2 || r === 2) return 1; return 0; }; if (dfs(root) === 0) cameras++; return cameras;};class Solution { private int cameras = 0;
private int dfs(TreeNode n) { if (n == null) return 1; // null counts as covered int l = dfs(n.left); int r = dfs(n.right); if (l == 0 || r == 0) { cameras++; return 2; } if (l == 2 || r == 2) return 1; return 0; }
public int minCameraCover(TreeNode root) { if (dfs(root) == 0) cameras++; return cameras; }}function minCameraCover(root: TreeNode | null): number { let cameras = 0; const dfs = (n: TreeNode | null): number => { if (!n) return 1; // null counts as covered const l = dfs(n.left), r = dfs(n.right); if (l === 0 || r === 0) { cameras++; return 2; } if (l === 2 || r === 2) return 1; return 0; }; if (dfs(root) === 0) cameras++; return cameras;}Editorial#
Three-state DFS is the cleanest framing. Bottom-up greedy chooses to place a camera at the lowest level needed. Placing cameras at parents of leaves (rather than leaves themselves) is optimal because a parent-camera covers 3 nodes vs a leaf-camera’s 2.
Complexity#
- Time: O(n).
- Space: O(h).
Concept revision#
Related#