968. Binary Tree Cameras
Tree, Depth-First Search, DP, Binary Tree, DFS ·Problem Statement
link: LeetCode.cn LeetCode 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:
Input: root = [0,0,null,0,0]
Output: 1
Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
Constraints: The number of nodes in the tree is in the range [1, 1000]. Node.val == 0
Solution Approach
The solution uses a depth-first search (DFS) approach to determine the minimum number of cameras required by evaluating each node’s state—whether it has a camera, is covered by a camera, or needs a camera—through dynamic programming.
Algorithm
- DFS with State Tracking: The solution uses depth-first search (DFS) to traverse the tree, where each node returns three states: the minimum cameras needed if the node has a camera, if the node is covered by a camera, and if the node is not covered.
- Dynamic Programming: For each node, the algorithm calculates the minimum number of cameras required by considering different scenarios—placing a camera at the node, ensuring the node is covered by its children, or relying on its parent for coverage.
- Minimizing Camera Placement: The result is derived from selecting the optimal state at the root node that ensures the entire tree is monitored with the fewest cameras possible, based on the aggregated results from its children.
Complexity
time complexity: O(n) space complexity: O(h)
Implement
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def minCameraCover(self, root: TreeNode) -> int:
def dfs(root: TreeNode) -> List[int]:
if not root:
return [float("inf"), 0, 0]
la, lb, lc = dfs(root.left)
ra, rb, rc = dfs(root.right)
a = lc + rc + 1
b = min(a, la + rb, ra + lb)
c = min(a, lb + rb)
return [a, b, c]
a, b, c = dfs(root)
return b