LeetCode 968. 监控二叉树

◎

本节目标

用后序三态标记节点的覆盖关系，贪心放置最少摄像头。

题意与约束

摄像头覆盖父、自己和直接子节点，求覆盖整棵二叉树的最少摄像头数。

第一反应与重复子问题

节点是否安全取决于子节点是否未覆盖或已装相机，因此仅记录“选或不选”不够。

状态定义与转移推导

后序状态为未覆盖 0、装相机 1、已覆盖 2。任一子节点未覆盖则当前装相机；任一子节点有相机则当前已覆盖；否则当前未覆盖。

正确性依据

未覆盖子节点只能由当前节点或其父覆盖，后序时在当前节点装相机不会劣于推迟；三态完整表达这种局部依赖。

样例执行过程

在 [0,0,null,0,0] 的内部节点放置一台相机，可同时覆盖根、自己和两个叶子。

代码实现

C++

C++17

#include <functional>
using namespace std;

class Solution {
public:
    int minCameraCover(TreeNode* root) {
        int cameras = 0;
        function<int(TreeNode*)> dfs = [&](TreeNode* node) {
            if (!node) {
                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;
        };
        int rootState = dfs(root);
        return cameras + (rootState == 0);
    }
};

Python

Python 3

class Solution:
    def minCameraCover(self, root):
        if not root:
            return 0

        cameras = 0
        states = {}
        stack = [(root, False)]
        while stack:
            node, visited = stack.pop()
            if not node:
                continue
            if visited:
                left = states.get(id(node.left), 2)
                right = states.get(id(node.right), 2)
                if left == 0 or right == 0:
                    cameras += 1
                    states[id(node)] = 1
                elif left == 1 or right == 1:
                    states[id(node)] = 2
                else:
                    states[id(node)] = 0
            else:
                stack.append((node, True))
                stack.append((node.right, False))
                stack.append((node.left, False))
        return cameras + (states[id(root)] == 0)

复杂度分析

每个节点只进行常数次处理，时间 O(n)。C++ 实现使用递归，调用栈为 O(h)；Python 实现使用显式栈并保存每个节点的状态，额外空间为 O(n)。

边界与易错点

空孩子视为已覆盖；遍历完成后根若仍未覆盖，需要补一台相机。计数必须在每次调用开始时重置。

模式迁移

覆盖、守卫和最小支配类树题常需要多于二个状态，先写清每个状态的语义再转移。回到树形动态规划。