Hard

题目描述

给定一个二叉树的根节点 root，我们在树的节点上安装摄像头。节点上的每个摄像头都可以监视其父对象、自身及其直接子对象。

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

示例 1：

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

示例 2：

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

提示：

  • 树中节点的数量在 [1, 1000] 范围内
  • Node.val == 0

解题思路

这是一个树形 DP 问题，关键是要确定每个节点的状态以及状态转移关系。

我们可以为每个节点定义三种状态：

  1. 状态 0：该节点未被覆盖，需要父节点放置摄像头
  2. 状态 1：该节点被覆盖，但自身没有摄像头
  3. 状态 2：该节点放置了摄像头

采用后序遍历，从叶子节点开始向上计算：

状态转移规则：

  • 对于叶子节点：返回状态 0（未被覆盖）
  • 对于内部节点：
    • 如果任一子节点未被覆盖（状态 0），当前节点必须放摄像头（状态 2）
    • 如果任一子节点有摄像头（状态 2），当前节点被覆盖（状态 1）
    • 如果所有子节点都被覆盖但无摄像头（状态 1），当前节点未被覆盖（状态 0）

特殊处理： 如果根节点最终状态为 0（未被覆盖），需要额外在根节点放置一个摄像头。

这种贪心策略能保证摄像头数量最少，因为我们优先让叶子节点的父节点放置摄像头，这样能覆盖更多节点。

代码实现

class Solution {
public:
    int cameras = 0;
    
    int minCameraCover(TreeNode* root) {
        cameras = 0;
        int rootState = dfs(root);
        // 如果根节点未被覆盖，需要在根节点放摄像头
        if (rootState == 0) cameras++;
        return cameras;
    }
    
private:
    // 返回值：0-未被覆盖，1-被覆盖但无摄像头，2-有摄像头
    int dfs(TreeNode* node) {
        if (!node) return 1; // 空节点视为被覆盖
        
        int left = dfs(node->left);
        int right = dfs(node->right);
        
        // 如果任一子节点未被覆盖，当前节点必须放摄像头
        if (left == 0 || right == 0) {
            cameras++;
            return 2;
        }
        
        // 如果任一子节点有摄像头，当前节点被覆盖
        if (left == 2 || right == 2) {
            return 1;
        }
        
        // 所有子节点都被覆盖但无摄像头，当前节点未被覆盖
        return 0;
    }
};

class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        self.cameras = 0
        
        def dfs(node):
            if not node:
                return 1  # 空节点视为被覆盖
            
            left = dfs(node.left)
            right = dfs(node.right)
            
            # 如果任一子节点未被覆盖，当前节点必须放摄像头
            if left == 0 or right == 0:
                self.cameras += 1
                return 2
            
            # 如果任一子节点有摄像头，当前节点被覆盖
            if left == 2 or right == 2:
                return 1
            
            # 所有子节点都被覆盖但无摄像头，当前节点未被覆盖
            return 0
        
        root_state = dfs(root)
        # 如果根节点未被覆盖，需要在根节点放摄像头
        if root_state == 0:
            self.cameras += 1
        
        return self.cameras

public class Solution {
    private int cameras = 0;
    
    public int MinCameraCover(TreeNode root) {
        cameras = 0;
        int rootState = Dfs(root);
        // 如果根节点未被覆盖，需要在根节点放摄像头
        if (rootState == 0) cameras++;
        return cameras;
    }
    
    private int Dfs(TreeNode node) {
        if (node == null) return 1; // 空节点视为被覆盖
        
        int left = Dfs(node.left);
        int right = Dfs(node.right);
        
        // 如果任一子节点未被覆盖，当前节点必须放摄像头
        if (left == 0 || right == 0) {
            cameras++;
            return 2;
        }
        
        // 如果任一子节点有摄像头，当前节点被覆盖
        if (left == 2 || right == 2) {
            return 1;
        }
        
        // 所有子节点都被覆盖但无摄像头，当前节点未被覆盖
        return 0;
    }
}

var minCameraCover = function(root) {
    let cameras = 0;
    
    function dfs(node) {
        if (!node) return 2;
        
        let left = dfs(node.left);
        let right = dfs(node.right);
        
        if (left === 0 || right === 0) {
            cameras++;
            return 1;
        }
        
        if (left === 1 || right === 1) {
            return 2;
        }
        
        return 0;
    }
    
    return dfs(root) === 0 ? cameras + 1 : cameras;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n)，其中 n 是树中节点的数量，每个节点只访问一次
空间复杂度O(h)，其中 h 是树的高度，递归调用栈的深度

相关题目