You are given the root
of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.
Return the minimum number of cameras needed to monitor all nodes of the tree.
Example 1:
Input: root = [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.
Example 2:
Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.
Constraints:
[1, 1000]
.Node.val == 0
You are given the root of a binary tree. You need to install cameras on the tree nodes such that each camera at a node can monitor its parent, itself, and its immediate children. The goal is to find the minimum number of cameras needed to monitor all nodes of the tree.
A brute-force approach would involve trying all possible combinations of camera placements. For each node, we can either place a camera or not. We would then check if the current camera placement monitors all nodes. This is a highly inefficient solution.
Big O Analysis
This solution is computationally infeasible for larger trees.
A more efficient approach involves a greedy algorithm combined with recursion. We can traverse the tree in a post-order manner. For each node, we can have three states:
We can implement the following logic during the post-order traversal:
For the root node, if it's not covered (state 0), we need to install a camera.
Big O Analysis
Edge Cases
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def minCameraCover(root: TreeNode) -> int:
count = 0
def dfs(node):
nonlocal count
if not node: # Null node is considered covered
return 1
left = dfs(node.left)
right = dfs(node.right)
if left == 0 or right == 0:
count += 1
return 2 # Install camera
elif left == 2 or right == 2:
return 1 # Node is covered
else:
return 0 # Node is not covered
if dfs(root) == 0:
count += 1 # Install camera at root if needed
return count
count
variable to track the number of cameras.dfs
.dfs
on the left and right children.count
and return 2 (install camera).count
.count
.