LeetCode: 968. Binary Tree Cameras

题目¶

原题地址： https://leetcode.com/problems/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

后续遍历二叉树，从下往上看，当把摄像头都放在节点的父节点上的时候就可以达到最少摄像头的要求，因为这种情况下一个摄像头可以监控最多4个节点：

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

有两个特殊的 case:

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

这个思路的 Python 代码类似下面这样：

# 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

参考资料¶

https://leetcode.com/problems/binary-tree-cameras/

题目¶

解法¶

参考资料¶

Comments