# 968 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:

``````    o
/
C
/ \
o   o

Input: root = [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.
``````

Example 2:

``````      o
/
C
/
o
/
C
\
o

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`
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 `````` ``````# Definition for a binary tree node. # 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: Optional[TreeNode]) -> int: self.ans = 0 covered = {None} def dfs( cur: Optional[TreeNode], parent: Optional[TreeNode]=None ) -> None: if not cur: return dfs(cur.left, cur) dfs(cur.right, cur) if ( # if a node has no parent and it is not covered, # we must place a camera here (not parent and cur not in covered) or # if a node has children that are not covered by a camera, # then we must place a camera here (cur.left not in covered or cur.right not in covered) ): self.ans += 1 covered.update({cur, parent, cur.left, cur.right}) dfs(root) return self.ans``````