LeetCode 968. 监控二叉树

2022-07-18 HGNULB 约 9 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

✅ 968. 监控二叉树

题意分析

题目给一棵二叉树，允许在任意节点上安装监控。一台监控的作用范围只有三层里的一小片：它自己、它的父节点、它的两个直接孩子。要求所有节点都被至少一台监控看到，问最少装几台。

「覆盖」和「安装」是两件必须分开的事。一个节点被覆盖，可能是因为它自己装了，也可能是因为它的父亲装了，还可能是因为它的某个孩子装了。仅仅记录一个节点「是否已被覆盖」的布尔值，不足以让它的父亲做决策，因为父亲还想知道这个孩子有没有在自己身上装相机。

约束里节点数不超过 1000，深度可能接近 1000，说明可以做一次线性的树上遍历，但递归深度需要留意；同时节点值全为 0，值本身不携带任何信息，所有信息都来自树的形状。

边界上要留意：空树的答案是 0；只有一个节点的树答案是 1，因为它没有父亲也没有孩子，只能自己装；根节点没有父亲，这意味着「等父亲来覆盖我」这条退路在根上是不存在的，必须单独兜底。

解法：后序贪心状态递归

核心思路

最朴素的做法是把每个节点看成装或不装的二元选择，枚举全部 $2^n$ 种方案再逐个验证覆盖性。这在 1000 个节点的规模下毫无可行性，但它提示了一件事：每个节点的决策只影响它周围三层，节点之间的耦合是极其局部的。

瓶颈在于暴力把所有节点的决策当成互相独立的自由变量同时枚举，而实际上一旦子树的状态确定，当前节点的最优选择几乎没有回旋余地。要利用这一点，关键是找出决策的方向。

关键观察是：叶子节点上永远不应该放相机。设想某个最优方案在叶子上放了一台，把它挪到叶子的父亲身上，原本被覆盖的（叶子自己、叶子的父亲）依然被覆盖，而且额外白赚了父亲的兄弟位置和祖父。也就是说，相机往上挪一层覆盖范围只增不减，代价不变，因此存在一个最优解满足「相机只装在有孩子亟需覆盖的节点上」。这就把决策方向定死为自底向上：先处理完子树，再看当前节点是否被逼着装相机。

由此确定每个节点向父亲汇报的状态定义：dfs(node) 返回三个值之一 —— HAS_CAMERA 表示这个节点自己装了相机，COVERED 表示它已经被覆盖但自己没装，NEED_COVER 表示它还没被任何相机覆盖、正等着父亲出手。三个状态恰好穷尽了父亲需要知道的全部信息：孩子是 NEED_COVER 就说明父亲不得不装（再不装这个孩子就没人管了，因为孩子的子树已经处理完，唯一还能覆盖它的就是父亲）；孩子是 HAS_CAMERA 说明父亲已经被顺带覆盖；两个孩子都只是 COVERED 则父亲既没被覆盖也不急着装，把需求上抛给祖父更划算。

空节点必须返回 COVERED。这不是为了「正确描述空节点」，而是为了让叶子节点自然地得到 NEED_COVER：如果空节点返回 NEED_COVER，叶子会被自己的两个空孩子逼着装相机，直接违背了上一段刚证明的贪心方向。

最后，根节点没有父亲兜底，所以整个递归返回后，若根的状态仍是 NEED_COVER，必须补装一台。

解题步骤

定义三个常量 HAS_CAMERA、COVERED、NEED_COVER，用一个外部计数器累计已安装的相机数。为什么用计数器而不是让递归返回台数：返回值已经被状态占用，而台数是全局累加量，两者职责分开更不容易写错。

递归出口：节点为空时返回 COVERED。为什么不是 NEED_COVER：空孩子若也来索要覆盖，叶子就被迫装相机，破坏「相机上移不劣」的贪心结论。

对非空节点，先递归左孩子再递归右孩子，拿到两个状态之后才开始判断。为什么必须后序：当前节点是否需要装相机，完全取决于孩子有没有被覆盖，先序或中序会在信息不全时做决策。

第一优先判断：只要左右孩子中任意一个是 NEED_COVER，当前节点立刻装相机，计数加一并返回 HAS_CAMERA。为什么这条排在最前：这是唯一的强制情形，孩子的子树已处理完毕，除了当前节点再无人能覆盖它，漏判会直接导致答案不合法。

第二优先判断：左右孩子中任意一个是 HAS_CAMERA，当前节点被孩子覆盖，返回 COVERED。注意这一步不能提到上一步之前，否则「一个孩子有相机、另一个孩子却缺覆盖」的节点会被误判成安全。

其余情况（两个孩子都是 COVERED）返回 NEED_COVER，把覆盖需求交给父亲。为什么不在这里主动装：装了只能覆盖自己和已被覆盖的孩子，纯浪费；交给父亲则能顺带覆盖父亲和祖父。

递归结束后检查根的返回值，若为 NEED_COVER 则计数再加一，返回计数。为什么只对 NEED_COVER 补装：COVERED 和 HAS_CAMERA 都说明根已经被看到了。

以 root = [0,0,null,0,null,0,null,null,0] 走一遍：这棵树是一条向左下延伸的链，记根为 A，A 的左孩子 B，B 的左孩子 C，C 的左孩子 D，D 的右孩子 E，其余位置全空。

先递归到最深处 E。E 的左右孩子都是空，各返回 COVERED，没有 NEED_COVER 也没有 HAS_CAMERA，于是 E 返回 NEED_COVER，计数仍为 0。

回到 D。D 的左孩子为空返回 COVERED，右孩子 E 返回 NEED_COVER，命中第一条判断，D 装相机，计数变成 1，D 返回 HAS_CAMERA。这台相机同时覆盖了 D、E 和 D 的父亲 C。

回到 C。左孩子 D 返回 HAS_CAMERA，右孩子为空返回 COVERED，没有 NEED_COVER，命中第二条判断，C 返回 COVERED，计数保持 1。

回到 B。左孩子 C 返回 COVERED，右孩子为空返回 COVERED，两条判断都不命中，B 返回 NEED_COVER，计数保持 1。

回到根 A。左孩子 B 返回 NEED_COVER，命中第一条判断，A 装相机，计数变成 2，A 返回 HAS_CAMERA。这台相机覆盖 A、B。

递归结束，根的状态是 HAS_CAMERA 而非 NEED_COVER，不需要补装，最终答案为 2，两台相机分别在 D 和 A 上，五个节点 A、B、C、D、E 全部被覆盖。

再看根需要兜底的场景：单节点树 root = [0]，两个空孩子都返回 COVERED，根返回 NEED_COVER，递归内部一台也没装，靠最后那次根检查把计数补成 1，答案正确。

代码实现

class Solution {
    // 对每个节点只需要区分三种状态：自己有相机、自己已被覆盖、自己还需要父节点覆盖。
    private static final int HAS_CAMERA = 0;
    private static final int COVERED = 1;
    private static final int NEED_COVER = 2;

    private int cameras;

    public int minCameraCover(TreeNode root) {
        if (dfs(root) == NEED_COVER) {
            cameras++;
        }

        return cameras;
    }

    private int dfs(TreeNode node) {
        if (node == null) {
            return COVERED;
        }

        int left = dfs(node.left);
        int right = dfs(node.right);
        if (left == NEED_COVER || right == NEED_COVER) {
            cameras++;
            return HAS_CAMERA;
        }

        if (left == HAS_CAMERA || right == HAS_CAMERA) {
            return COVERED;
        }

        return NEED_COVER;
    }
}

func minCameraCover(root *TreeNode) int {
    // 对每个节点只需要区分三种状态：自己有相机、自己已被覆盖、自己还需要父节点覆盖。
    const (
        hasCamera = 0
        covered   = 1
        needCover = 2
    )

    cameras := 0

    var dfs func(node *TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return covered
        }

        left := dfs(node.Left)
        right := dfs(node.Right)
        if left == needCover || right == needCover {
            cameras++
            return hasCamera
        }

        if left == hasCamera || right == hasCamera {
            return covered
        }

        return needCover
    }

    if dfs(root) == needCover {
        cameras++
    }

    return cameras
}

复杂度分析

时间复杂度：$O(n)$，每个节点恰好被递归访问一次，节点内部只做常数次状态比较，没有任何重复子问题被重算。

空间复杂度：$O(h)$，其中 $h$ 是树高，唯一开销是递归栈；这棵树可能退化成链，最坏情况下 $h = n$。

关键点总结

当子结构向父结构汇报的信息不止「成功/失败」两种时，果断把返回值升级成枚举状态。这里的三态划分是整道题的胜负手：状态少一个就丢信息，多一个就冗余。

贪心方向要靠交换论证定下来，不能靠直觉。「把叶子上的相机上移一层，覆盖只增不减」这句话既确定了自底向上的处理顺序，也直接推出了空节点必须返回 COVERED。

判断分支的先后顺序本身携带贪心语义。强制情形（孩子亟需覆盖）必须排在可选情形（孩子已有相机）之前，顺序一换，正确性就没了。

根节点缺少父亲这条退路，凡是「把需求上抛给父亲」的树上递归，都要在递归外面补一次兜底检查。

面试视角：面试官几乎一定会问「为什么这是贪心而不是 DP，能不能证明」。准备好交换论证的那两句话，比背下三个状态更重要。

面试视角：可以主动提一句这题也能写成树形 DP，对每个节点维护「装相机 / 不装但被覆盖 / 不装也没被覆盖」三个最小代价并取 min，复杂度同样是 $O(n)$，但常数更大、代码更长；说明你知道贪心是这个 DP 的坍缩形式，而不是碰巧凑对。

易错点总结

错误写法：空节点返回 NEED_COVER。用例 [0,0,null,0,0] → 两个叶子各自被空孩子逼着装相机，随后根又因右空孩子索要覆盖再装一台，答案从正确的 1 变成 3。

错误写法：空节点返回 HAS_CAMERA。用例 [0] → 根被两个空孩子「覆盖」而返回 COVERED，最后的根检查也不触发，答案为 0，但正确答案是 1。

错误写法：递归结束后忘记检查根节点状态。用例 [0] → 递归内部一台相机都没装，直接返回 0，正确答案是 1。

错误写法：根检查写成 if (dfs(root) != HAS_CAMERA) cameras++。用例 [0,0,null,0,0] → 根返回的是 COVERED，本已被孩子覆盖却又补装一台，答案从 1 变成 2。

错误写法：把 HAS_CAMERA 的判断提到 NEED_COVER 之前。用例 [0,0,0,0,null,null,null]（根的左孩子有一个叶子、根的右孩子是叶子）→ 根看到左子树已有相机就返回 COVERED，右边那个叶子无人覆盖，答案从 2 变成 1 且方案非法。

错误写法：返回 HAS_CAMERA 时忘记把计数加一。用例任意非空树 → 相机装了但没被统计，答案恒为 0 或严重偏小。

错误写法：用一个布尔值表示「是否已被覆盖」来代替三态。用例任意树 → 父节点无法区分孩子是「自己装了相机」还是「被更下层覆盖」，于是无法判断自己是否已被孩子照到，只能保守地多装，答案偏大。

错误写法：先决定当前节点是否装相机再递归子树。用例任意深度大于 2 的树 → 决策依赖尚未计算出的子树状态，读到的是初始值，结果不可预测。

错误写法：用「叶子节点」而不是「空节点」作为递归出口。用例 [0,0,null,0,null,0,null,null,0] 这类只有单侧孩子的链 → 单孩子节点既不是叶子也无法从空侧拿到状态，分支容易漏写，返回值含义在不同路径上不一致。

相似题目

题目	难度	考察点
337. 打家劫舍 III	中等	同样是节点选与不选，但收益可加，必须写成树形 DP
979. 在二叉树中分配硬币	中等	后序向上传递「盈亏差」这一带符号的数值而非枚举状态
124. 二叉树中的最大路径和	困难	返回值与全局答案语义不同，需在节点处单独结算
543. 二叉树的直径	简单	后序返回深度、答案取跨节点组合，是该模式的最简形态