Binary Tree Cameras Python Solution with Tests

lcpy gen -n 968   # by problem number
lcpy gen -s binary_tree_cameras   # by problem name

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

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.

from leetcode_py import TreeNode


class Solution:
    # Time: O(n)
    # Space: O(h) for the recursion stack
    def min_camera_cover(self, root: TreeNode[int] | None) -> int:
        cameras = 0

        # Post-order status per subtree: 0 needs a camera, 1 covered, 2 holds a camera
        def dfs(node: TreeNode[int] | None) -> int:
            nonlocal cameras
            if node is None:
                return 1
            left = dfs(node.left)
            right = dfs(node.right)
            if left == 0 or right == 0:
                cameras += 1
                return 2
            if left == 2 or right == 2:
                return 1
            return 0

        if dfs(root) == 0:
            cameras += 1
        return cameras