监控二叉树

Leetcode Link: 968. 监控二叉树 - 力扣（LeetCode）

题目

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

解法一

思路： 画图很好解决，并且通过画图，尝试，可以得知最好的方法就是从叶子节点开始往上放置。显然，应该是后序遍历。

对于一个节点，我们设置三个返回值表示三种不同的状态（有且只有这三种状态） 1 : 该点被监控了（挨着摄像机） 0 ：该点放置了摄像机 -1 ：该点没有被监控

采用贪心的方案，如果叶子节点有任意一个没有被监控 (-1)，则都需要在该点放置一个摄像头

所有的情况如下：

1. 如果叶子节点有任意一个没有被监控 (-1)，则都需要在该点放置一个摄像头
2. 如果两个叶子节点都是被监控的 1，那么该点就应该是未被监控的状态（-1）
3. 如果两个叶子节点中一个是 0 一个是 1，或者两个全是 0，则表示该点处于监控之中 (1)

然而，还有如下两个问题需要注意： a. 本题中如果该节点没有被监控，我们是通过在父节点放置摄像头的。但是如果头节点没有被监控，它是没有父节点的，所以只会返回一个状态，但是不能走到放置监控并 res++ 的那一步了，所以需要我们自己补充上 b. 叶子节点一定是返回 -1 的；对于空节点，应该返回的是 1。返回 0 会导致莫名出现一个覆盖区域，返回 -1 会导致浪费摄像头 因此我们可以把空节点设置为我们的base case

题解：

class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        def recur(node):
            nonlocal res
            # base case，空节点返回1
            # 同样能够保证叶子节点返回 -1
            if not node:
                return 1
 
            left = recur(node.left) 
            right = recur(node.right) 
            
            # 两边有一边没有被监控，则放置个摄像头
            if left == -1 or right == -1:
                res += 1
                return 0
            # 两边都在覆盖范围里，则不用放置摄像头，在这个节点的父节点放一个就行
            elif left == 1 and right == 1:
                return -1
            # 两边有一边放置了摄像头，该点就算是被监控了
            # 注意判断顺序，在这里判断会简单一些，一些情况被合并了
            elif left == 0 or right == 0:
                return 1
 
        res = 0
        # 一定要考虑头节点，如果头节点是-1，他是没有父节点放置摄像机的，所以必需在该点放置
        if recur(root) == -1:  
            res += 1
        return res

启发和联系

这个问题开始干瞪眼不会做，但是一画图就会了。

最好还是画图