968. 监控二叉树（Binary Tree Cameras）

频次 ★★★★ · 难度 🔴 · 高频：字节/阿里

题目

给定一棵二叉树，在节点上安装摄像头。每个摄像头可以监控自身、父节点和直接子节点。求覆盖整棵树所需的最少摄像头数量。

示例：

输入: [0,0,null,0,0]
输出: 1 （在根节点安装一个摄像头即可覆盖所有节点）

输入: [0,0,null,0,null,0,null,null,0]
输出: 2

思路

贪心 + 后序遍历（状态 DP）：从叶子节点向上，尽量不在叶子节点安装摄像头，而在叶子节点的父节点安装（覆盖范围最大）。每个节点返回三种状态：

• 0：当前节点无覆盖
• 1：当前节点有摄像头
• 2：当前节点有覆盖（被父节点或子节点覆盖，但自身无摄像头）

后序遍历，根据左右子节点的状态决定当前节点的状态：

• 左右任一为 0（无覆盖）→ 当前必须装摄像头，返回 1
• 左右任一为 1（有摄像头）→ 当前被覆盖，返回 2
• 左右都是 2（有覆盖但无摄像头）→ 当前无覆盖，返回 0

根节点最后单独检查：如果根节点返回 0（无覆盖），需要额外加一个摄像头。

代码

private int cameras = 0;
 
public int minCameraCover(TreeNode root) {
    if (dfs(root) == 0) cameras++;   // 根节点无覆盖，需要额外加摄像头
    return cameras;
}
 
// 返回：0=无覆盖 1=有摄像头 2=有覆盖
private int dfs(TreeNode node) {
    if (node == null) return 2;      // 空节点视为"有覆盖"，不影响父节点判断
 
    int left = dfs(node.left);
    int right = dfs(node.right);
 
    // 任一子节点无覆盖 → 当前必须装摄像头
    if (left == 0 || right == 0) {
        cameras++;
        return 1;
    }
 
    // 任一子节点有摄像头 → 当前被覆盖
    if (left == 1 || right == 1) {
        return 2;
    }
 
    // 左右子节点都有覆盖但无摄像头 → 当前无覆盖，等父节点来覆盖
    return 0;
}

复杂度

• 时间：O(n) —— 每个节点访问一次
• 空间：O(h) —— 递归栈深度，h 为树高

边界条件

• 空树：返回 0
• 只有一个节点：返回 1（必须装一个摄像头）
• 单链（每个节点只有一个子节点）：摄像头间隔安装，约 n/2 个
• 满二叉树：最优策略是隔层安装，约 n/3 个

变式

• 337. 打家劫舍 III：同为树形 DP，但状态不同（偷/不偷 vs 无覆盖/有摄像头/有覆盖）
• 979. 在二叉树中分配硬币：树形贪心 + 后序遍历

易错点

• 状态定义的顺序：判断顺序必须是 0→1→2，不能颠倒。先判断”有无覆盖”（紧急），再判断”是否被覆盖”（安全），最后才是”等父节点覆盖”
• 空节点返回 2 而非 0：空节点不需要覆盖，返回 2（有覆盖）避免影响父节点的判断。如果返回 0，父节点会误判为需要装摄像头
• 根节点需要单独检查：后序遍历后根节点可能返回 0（左右子节点都返回 2），此时需要额外加一个摄像头
• cameras 是全局变量：后序遍历过程中累加，不能作为返回值的一部分

面试追问

• 为什么在叶子节点的父节点装摄像头？ 贪心：摄像头覆盖范围是”自身+父+子”，装在叶子节点只能覆盖叶子和其父，装在叶子父节点可以覆盖叶子、自身、父共三层。从下往上，让摄像头尽量装在上层，覆盖范围最大
• 状态为什么是 3 个而不是 2 个？ 2 个状态（有/无摄像头）无法区分”被覆盖”和”无覆盖”两种情况。无覆盖需要父节点装摄像头，被覆盖则不需要，区分这两种情况是关键

关联题

• 同套路：337. 打家劫舍 III —— 树形 DP 另一经典
• 进阶：979. 在二叉树中分配硬币 —— 树形贪心
• 知识点：树形贪心之后序遍历状态机模板见贪心