📃 题目描述

题目链接：968. 监控二叉树 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

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

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

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

示例 1：

输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。

示例 2：

输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

🔔 解题思路

重点：摄像头不要放在叶子节点上，摄像头可以覆盖上中下三层，如果把摄像头放在叶子节点上，就浪费的一层的覆盖。

⭐ 所以我们要从下往上看（后序遍历）：

局部最优：让叶子节点的父节点安摄像头，所用摄像头最少；整体最优：全部摄像头数量所用最少

此时，大体思路就是从下到上，先给叶子节点父节点放个摄像头，然后隔一个节点放一个摄像头，直至到二叉树头结点。

此时这道题目还有两个难点：

1. 二叉树如何从下往上遍历？（后序遍历，左右根）
2. 如何隔一个节点放一个摄像头？

我们来列举下每个节点可能的状态：

1. 有摄像头

2. 没有摄像头，又分为：

   2.1 被覆盖到

   2.2 没有被覆盖到

所以实际上就是 3 个状态，我们可以用 3 个数字来表示：

【0】：没有被覆盖到

【1】：被覆盖到

【2】：有摄像头

那么突破点在哪里，也就是说这棵树的初始值该怎么设置？这些状态的判断肯定得有一个初始值才能运转起来对吧。

突破点就是空节点！

考虑下空节点的状态是什么？

• 没有被覆盖到？那不行，一个叶子节点对应两个空节点，要是空节点的状态是没有被覆盖到，那叶子节点就需要放摄像头了

• 有摄像头？那不行，依据题意，节点上的每个摄影头可以监视其父对象、自身及其直接子对象。空结点如果有摄像头的话，那么其父节点也就是叶子节点的状态就是被覆盖到，那么这个叶子节点的父节点就不会在放置摄像头了，显然不符合逻辑。

• 所以空节点的状态只能是被覆盖到，这样其父节点也就是叶子节点就不需要放置摄像头，而且也可以在这个叶子节点的父节点放置摄像头了

  if (cur == null) {
  	return 1
  }
  

确定了突破口是空节点后，我们再来处理非叶子节点（记为 cur）的情况：

根据我们从下往上处理的后序遍历的逻辑，我们的目标就是要让 cur 的左右孩子都能被覆盖到！

1. 左右孩子都有覆盖：说明左右孩子的孩子有摄像头，当然这个摄像头没法覆盖到 cur，所以 cur 应该就是无覆盖的状态了

   if (cur.left == 1 && cur.right == 1) {
   	return 0;
   }
   

2. 左右孩子至少有一个无覆盖的情况：此时需要在 cur 节点处放置摄像头

   if (cur.left == 0 || cur.right == 0) {
       res ++; // 摄像头数量
       return 2;
   }
   

3. 左右节点至少有一个有摄像头：此时 cur 节点被覆盖

   if (cur.left == 2 || cur.right == 2) {
   	return 1;
   }
   

   如果左节点有摄像头【2】，右节点没摄像头并且也没被覆盖【0】怎么办呢？

   这种情况在第 2 点已经判断过了

所有情况处理完之后，我们还需要判断下根节点是否被覆盖，若没有，则需要添加摄像头

class Solution {
    // 摄像头数量
    private int res = 0;

    // 没有被覆盖到
    private static int UNCOVERED = 0;
    // 被覆盖到
    private static int COVERED = 1;
    // 有摄像机
    private static int CAMERA = 2;

    public int minCameraCover(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // traversal(root) 返回的是 root 节点的状态
        if (traversal(root) == UNCOVERED) {
            res ++;
        }
        return res;
    }

    // 返回 cur 节点的状态
    private int traversal(TreeNode cur) {
        if (cur == null) {
            return COVERED;
        }
        
        int left = traversal(cur.left);
        int right = traversal(cur.right);

        // 左右孩子都被覆盖
        if (left == COVERED && right == COVERED) {
            return UNCOVERED;
        }

        // 左右孩子至少有一个没被覆盖
        if (left == UNCOVERED || right == UNCOVERED) {
            res ++;
            return CAMERA;
        }

        // 左右孩子至少有一个有摄像头
        if (left == CAMERA || right == CAMERA) {
            return COVERED;
        }
        
        // 不会走到这里
        return -1;
    }
}

💥 复杂度分析

• 空间复杂度：O(LogN)
• 时间复杂度：O(N)