# LeetCode: 968. Binary Tree Cameras

## 题目¶

Given a binary tree, we install cameras on the nodes of the tree.

Each camera at a node can monitor its parent, itself, and its immediate children.

Calculate the minimum number of cameras needed to monitor all nodes of the tree.

Example 1:

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

Example 2:

```Input: [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.
```

Note:

• The number of nodes in the given tree will be in the range [1, 1000].
• Every node has value 0.

## 解法¶

• 节点上有摄像头：STATUS_HAS_CAMERA
• 节点上没有摄像头，但是被其他节点上的摄像头所监控：STATUS_MONITOR_NO_CAMERA
• 节点上既没有摄像头也没有被其他摄像头所监控：STATUS_NOT_MONITOR

• 如果 left 和 right 节点其中有一个未被监控到的话(STATUS_NOT_MONITOR)，当前节点就应该放一个摄像头(STATUS_HAS_CAMERA)
• 如果 left 和 right 节点都是没有摄像头但是被监控的话(STATUS_MONITOR_NO_CAMERA)，为了达到最少的摄像头应该在当前节点的父节点上放摄像头， 即当前节点不要放摄像头(STATUS_NOT_MONITOR)
• 否则当前节点就是没有摄像头但是被监控(STATUS_MONITOR_NO_CAMERA)

• 对于没有子节点的节点，因为想把摄像头放到它的父节点上，所以需要把空的子节点节点的状态标记为 STATUS_MONITOR_NO_CAMERA
• 如果最终二叉树的根节点的状态是 STATUS_NOT_MONITOR 的话，需要在它上面放一个摄像头

```# 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:
STATUS_NOT_MONITOR = 0
STATUS_HAS_CAMERA = 1
STATUS_MONITOR_NO_CAMERA = 2

def minCameraCover(self, root):
self._number = 0

status = self._get_status(root)
if status == self.STATUS_NOT_MONITOR:
self._number += 1

return self._number

def _get_status(self, root):
# 空节点
if root is None:
return self.STATUS_MONITOR_NO_CAMERA

left = self._get_status(root.left)
right = self._get_status(root.right)

# left or right 至少有一个未被监控
if left == self.STATUS_NOT_MONITOR or right == self.STATUS_NOT_MONITOR:
self._number += 1
return self.STATUS_HAS_CAMERA

# left 和 right 都没有摄像头但是被监控了，为了把摄像头放到父节点，当前节点无摄像头也暂时未被监控
if left == self.STATUS_MONITOR_NO_CAMERA and right == self.STATUS_MONITOR_NO_CAMERA:
return self.STATUS_NOT_MONITOR

# 当前节点虽然没有摄像头但是被监控
return self.STATUS_MONITOR_NO_CAMERA
```