968. Binary Tree Cameras

Hard

---

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

# 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.camera = 0
        value = self.dfs(root)
        return self.camera + (1 if value == 2 else 0)
    
    def dfs(self, root):
        # NULL is monitored
        if root is None:
            return 1
        left = self.dfs(root.left)
        right = self.dfs(root.right)
        
        # Both are monitored, no monitoring required
        if left == 1 and right == 1:
            return 2
        
        # One of the child is not monitored
        if left == 2 or right == 2:
            self.camera += 1
            return 3
        return 1