0968. 监控二叉树【困难】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 贪心 + 后序遍历

1. 📝 题目描述

• leetcode

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

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

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

---

示例 1：

输入：[0,0,null,0,0]
输出：1

解释：
如图所示，一台摄像头足以监控所有节点。

---

示例 2：

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

解释：
需要至少两个摄像头来监视树的所有节点。
上图显示了摄像头放置的有效位置之一。

---

提示：

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

2. 🎯 s.1 - 贪心 + 后序遍历

js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minCameraCover = function (root) {
  // 节点状态：0-未覆盖，1-已覆盖但无摄像头，2-有摄像头
  let count = 0

  const dfs = (node) => {
    if (!node) return 1 // 空节点视为已覆盖

    const left = dfs(node.left)
    const right = dfs(node.right)

    // 如果子节点有未覆盖的，当前节点必须安装摄像头
    if (left === 0 || right === 0) {
      count++
      return 2
    }

    // 如果子节点有摄像头，当前节点被覆盖
    if (left === 2 || right === 2) {
      return 1
    }

    // 子节点都被覆盖但无摄像头，当前节点未覆盖
    return 0
  }

  // 如果根节点未覆盖，需要在根节点安装摄像头
  if (dfs(root) === 0) {
    count++
  }

  return count
}

• 时间复杂度：$O(n)$，其中 n 是树中节点数量，每个节点访问一次
• 空间复杂度：$O(h)$，其中 h 是树的高度，递归栈的空间开销

算法思路：

• 状态定义：每个节点有三种状态：0-未覆盖，1-已覆盖但无摄像头，2-有摄像头
• 后序遍历：从叶子节点向上处理，确保子节点状态已知后再决定当前节点的状态
• 贪心策略：优先从叶子节点的父节点开始安装摄像头，这样可以覆盖更多节点
• 状态转移：如果子节点有未覆盖的（状态0），当前节点必须安装摄像头（状态2）；如果子节点有摄像头（状态2），当前节点被覆盖（状态1）；如果子节点都被覆盖但无摄像头（状态1），当前节点未覆盖（状态0）
• 空节点处理：空节点视为已覆盖（状态1），避免叶子节点安装摄像头
• 根节点特殊处理：如果根节点未覆盖，需要在根节点安装摄像头