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.
class Solution:
def minCameraCover(self, root):
self.ans = 0
def dfs(node):
if not node:
return 0
val = dfs(node.left) + dfs(node.right)
if val == 0:
return 3
if val < 2:
return 0
self.ans += 1
return 1
return self.ans + 1 if dfs(root) > 2 else self.ansFollow-up:
What if we can install cameras on the edges of the tree instead of the nodes?
