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
Python3
# 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