Leetcode 968 Binary Tree Cameras

发表于 |

给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。

题意分析：
在一棵树中放置若干相机来监管所有的节点。每个相机可以监视当前节点，以及当前节点的父节点和子节点。

思路分析：
一棵树中的节点数是固定的，我们想用最少的相机来监管所有的节点，那么每个相机都要监管得足够多才行。

那么我们从树的最底部开始分析，如果在最后一层的某个节点A放置相机，那么这个相机最多能监管到2个节点，也就是A自身以及父节点B（可能不存在）。但如果将相机放到B节点，那么这个相机至少能监控2个节点，至多能监控4个节点，B自身，两个子节点，一个父节点。
而且为了点亮最底层的A节点，我们必须从A,B两个节点里面选一个，所以我们肯定选择B。
从这里我们可以看出，从下往上分析，对于当前还没被监控到的层来说，一个相机放在该层的上一层始终比放在该层要更优。那么贪心算法可行。

具体方法：
因为要从下至上分析，我这里先采用前序遍历将所有的节点存储下来，然后从最后一个开始分析。
对于遍历的节点，我们首先判断其是否已经被监控，若是则跳过，若否则在其父节点（若存在）处放置一个相机。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def minCameraCover(self, root):
        if not root.left and not root.right: return 1
        nums = []
        d = {root: None} # 使用d记录每个子节点的父节点
        q = collections.deque([root])
        while q:
            node = q.popleft()
            if node.left:
                d[node.left] = node
                q.append(node.left)
            if node.right:
                d[node.right] = node
                q.append(node.right)
            nums.append(node)
        
        dp = {}
        for i in range(len(nums)-1,-1,-1):
            parent = d[nums[i]]
            # 判断当前节点是否已经被监控
            if nums[i] in dp or nums[i].left in dp or nums[i].right in dp:
                continue
            dp[parent] = 1
        return sum(dp.values())