https://leetcode.com/problems/binary-tree-cameras/
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:
The number of nodes in the tree is in the range [1, 1000].
Node.val == 0
- code
class Solution:
def minCameraCover(self, root: Optional[TreeNode]) -> int:
covered = {None}
self.res = 0
def dfs(node, parent = None):
if node:
dfs(node.left, node)
dfs(node.right, node)
if node.left not in covered \
or node.right not in covered \
or (node not in covered and parent is None):
self.res += 1
covered.update({node, node.left, node.right, parent})
dfs(root)
return self.res