Shouyu

Appearance

监控二叉树 ​

题目描述 ​

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

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

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

题目链接：https://leetcode.cn/problems/binary-tree-cameras

文章讲解：https://programmercarl.com/0968.监控二叉树.html

思路 ​

其实这道题很不好想。我们好像不知道怎么放置才能使得最小摄像头数量最少。

但是我们好像知道，从题目示例上来看，叶子节点放监控摄像头是浪费。

那么从叶子节点往上，逐步的确立摄像头的位置。

从下往上考虑，可以省掉所有叶子节点，不用安装摄像头；如果从上往下考虑，那么最多就是省掉根节点的一个摄像头。

所以我们要从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！

局部最优推出全局最优，找不出反例，那么就按照贪心来！

遍历顺序 ​

遍历顺序显然就是后序遍历，因为任意一个节点是否放摄像头，取决于它的子节点有没有被监控到。显然每个节点应该有一个状态。

状态 ​

来看看这个状态应该如何转移，先来看看每个节点可能有几种状态：

有如下三种：

  • 该节点无覆盖
  • 本节点有摄像头
  • 本节点有覆盖

我们分别有三个数字来表示：

  • 0：该节点无覆盖
  • 1：本节点有摄像头
  • 2：本节点有覆盖

找不出第四个节点的状态了。

对于空节点，空节点的状态是什么呢？

假设空节点是叶子节点的空子节点，那么空节点不能是无覆盖的状态，这样叶子节点就要放摄像头了

空节点也不能是有摄像头的状态，这样叶子节点的父节点就没有必要放摄像头了，而是可以把摄像头放在叶子节点的爷爷节点上

这样空子节点的状态就必须是覆盖。这样，叶子节点才是不覆盖，继而把摄像头放在叶子节点的父亲身上。

单层递归逻辑 ​

现在我们应该考虑每个非空节点所遍历到的情况了。

  1. 如果左右节点都有覆盖，那么中间节点应该是无覆盖。
  2. 如果左右节点至少有一个无覆盖，那么中间节点必须放摄像头。
  3. 如果左右节点至少有一个摄像头，那么中间节点的状态应该是覆盖
  4. 还有一种特殊情况，头节点无覆盖的状态，result++。遍历完之后判断头节点的状态就行，不在单层递归的逻辑中。

对于头节点无覆盖的状态，因为头节点往上不可能再有节点能够覆盖它了，因此就必须往这个头节点上放摄像头。

对于二叉树的遍历，考虑空节点，在空节点终止是标准做法。空节点作为边界更符合树的递归特性。

如果在叶子节点终止，需要额外的空指针检查 - 在递归调用前必须检查子节点是否存在，逻辑稍微复杂 - 需要区分叶子节点和有子节点的情况，代码冗余 - 需要额外的if判断来避免空指针访问

代码实现 ​

C++
class Solution {
public:
    int result;
    int traversal(TreeNode* node) { // 这个函数接受一个节点，返回该节点的状态
        if (node == nullptr)
            return 2;
        int left = traversal(node->left);
        int right = traversal(node->right);
        if (left == 2 && right == 2) {
            return 0;
        }
        if (left == 0 || right == 0) {
            result++;
            return 1;
        }
        if (left == 1 || right == 1) {
            return 2;
        }
        return -1;
    }

    int minCameraCover(TreeNode* root) {
        result = 0;
        int rootVal = traversal(root);
        if (rootVal == 0)
            result++;
        return result;
    }
};