Sponsored
Sponsored
The greedy DFS solution is based on a bottom-up approach. We classify each node into one of three states: covered by a camera, has a camera, or needs a camera. A node needs a camera if its children are not covered. We use a post-order DFS strategy to ensure all children are addressed before deciding the current node's state. The optimal way to cover a subtree is to place a camera on nodes whose children are not covered.
Time Complexity: O(n), where n is the number of nodes in the tree, due to the DFS traversal of every node.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack space.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def minCameraCover(self, root: TreeNode) -> int:
9 self.min_cameras = 0
10
11 def dfs(node):
12 if not node:
13 return 2
14 left = dfs(node.left)
15 right = dfs(node.right)
16 if left == 0 or right == 0:
17 self.min_cameras += 1
18 return 1
19 return 2 if left == 1 or right == 1 else 0
20
21 if dfs(root) == 0:
22 self.min_cameras += 1
23 return self.min_camerasThe Python implementation uses recursion inside the DFS function to post-order traverse the tree. It increments `self.min_cameras` when a camera is needed because the node's children are not covered.
This approach leverages dynamic programming through a recursive function with memoization to reduce redundant calculations. Each node can have three states represented in a tuple: it has a camera, it's covered but doesn't have a camera, or it's not covered. Using this state information, the solution calculates camera placements strategically.
Time Complexity: O(n), where n is the number of nodes.
Space Complexity: O(n), due to memoization storage.
1from functools import lru_cache
2
3class TreeNode:
4 def
This solution uses dynamic programming with memoization to avoid redundant recursive calls. The function `dfs` returns a tuple of three states for each node: the cost of having a camera, being covered without a camera, and not being covered.
The first element, `dp0`, calculates cost when a camera is placed at the current node. The second, `dp1`, calculates when the node is covered without having a camera, and the third, `dp2`, calculates when the node itself isn't covered.