监控二叉树 | LeetCode-968 | 贪心算法

贪心练习题

---

LeetCode链接：968. 监控二叉树

---

1.题目描述

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

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

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

示例 1：

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

示例 2：

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

提示：

1. 给定树的节点数的范围是 [1, 1000]。
2. 每个节点的值都是 0。

2.题解

2.1 贪心算法

• 思路：
  • count 变量用于统计所需的摄像头总数。
  • 方法traversal用递归方式检查每个节点的状态：
    • 若节点为空，返回 2（视为已覆盖）。
    • 左右子节点检查的结果用于决定当前节点的状态。
  • 三种主要情况：
    • 若左右子节点都已覆盖，则当前节点未覆盖，需要返回 0。
    • 若左右子节点有任一未覆盖，则在当前节点放置摄像头，返回 1 并增加计数。
    • 若左右子节点至少有一个有摄像头，则当前节点已覆盖，返回 2。

class Solution {
    int count;
    // 定义方法 minCameraCover，接收一个树的根节点 root，返回所需的最小摄像头数量
    public int minCameraCover(TreeNode root) {
        // 初始化摄像头计数为 0
        count = 0;
        // 如果根节点未覆盖（返回 0），需要额外添加一个摄像头
        if (traversal(root) == 0) count++;
        // 返回总摄像头数量
        return count;
    }

    // 定义一个辅助方法 traversal，接收当前节点 cur，返回节点状态
    public int traversal(TreeNode cur) {
        // 如果当前节点为空，视为已覆盖状态
        if (cur == null) return 2;

        int left = traversal(cur.left);// 遍历左子节点
        int right = traversal(cur.right);// 遍历右子节点

        // 判断当前节点状态
        // 0：该节点未被覆盖
        // 1：当前节点有摄像头
        // 2：当前节点已被覆盖

        // 情况1：如果左右子节点均为已覆盖状态（返回 2），则当前节点未被覆盖
        if (left == 2 && right == 2)
            return 0;
        // 情况2：如果左右子节点中有一个未被覆盖（返回 0），则当前节点需要安装摄像头
        else if (left == 0 || right == 0) {
            count++;  // 安装摄像头
            return 1; // 当前节点有摄像头
        }
        // 情况3：如果左右子节点中至少有一个节点有摄像头（返回 1），则当前节点已被覆盖
        else if (left == 1 || right == 1)
            return 2;
        // 不应出现的情况，返回 -1（用于处理未知状态）
        else
            return -1;
    }
}