Skip to content

968. Binary Tree Cameras

Difficulty Topics

Description

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

Solution

binary-tree-cameras.py
# 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:
        NO_CAMERA, HAS_CAMERA, NOT_NEEDED = 0, 1, 2
        res = 0

        def go(node):
            nonlocal res

            if not node: return NOT_NEEDED

            l, r = go(node.left), go(node.right)

            if l == NO_CAMERA or r == NO_CAMERA:
                res += 1
                return HAS_CAMERA
            elif l == HAS_CAMERA or r == HAS_CAMERA:
                return NOT_NEEDED
            else:
                return NO_CAMERA

        if go(root) == NO_CAMERA:
            res += 1

        return res