Binary Tree Cameras
You are given the root of a binary tree. We install cameras on the nodes of the tree. Each camera at a node can monitor its parent, itself, and its children. Find the minimum number of cameras needed to monitor all nodes of the tree.
Constraints:
- The number of nodes in the tree is in the range [1, 1000].
- Node.val is 0.
Examples:
Input: [1,null,2,0,null,0,4]
Output: 2
Explanation: One possible solution is to install cameras at nodes 0 and 4.
Solutions
Depth-First Search
Time: O(N)Space: O(H)
We use a depth-first search to traverse the tree. For each node, we have three states: -1 (not covered), 0 (covered by children), and 1 (has camera). If a node is not covered by its children, we install a camera at the current node and increment the answer.
var minCameraCover = function (root) {
let ans = 0;
function dfs(node) {
if (!node) return 0;
const left = dfs(node.left);
const right = dfs(node.right);
if (left === -1 || right === -1) {
ans++;
return 1;
}
if (left === 1 || right === 1) return 0;
return -1;
}
if (dfs(root) === -1) ans++;
return ans;
};
Follow-up:
What if we can install cameras on the edges of the tree instead of the nodes?
