LeetCode 968二叉树摄像头WA：奇偶层放摄像头思路修正

原思路错误根源 #

你的解法基于一个不成立的假设：监控所有节点的最优方案，一定是把摄像头全部放在奇数层、或者全部放在偶数层。
这个假设只在满二叉树的特殊场景下近似成立，一旦树是斜链、或者存在空缺节点的结构，整层放置摄像头会产生大量冗余。
你遇到的失败测试用例本质是一条长度为6的斜链，结构如下：

层0（根）: 0
层1:      0
层2:        0
层3:          0
层4:            0
层5:              0

按你的算法，奇数层（0、2、4层）共3个节点，偶数层（1、3、5层）共3个节点，取最小值得到3。但实际最优解只需要2个摄像头：分别放在层1和层4的节点上——层1的摄像头覆盖层0、层1、层2的节点，层4的摄像头覆盖层3、层4、层5的节点，所有节点全覆盖，不需要整层安装。
摄像头的覆盖范围是「自身+父节点+直接子节点」，也就是跨3个相邻层，最优放置策略是隔2个节点放1个，不需要严格对齐到同一层，这就是你原思路计算结果偏大的核心原因。

思路修正说明 #

原思路里「整层全装/全不装」的核心逻辑本身存在缺陷，无法通过小调整得到正确结果。如果你希望保留分层遍历（也就是你原来按层处理的BFS框架），可以把原来的奇偶层计数逻辑，替换为层间状态递推：
给每个节点定义3种状态，从最底层向上逐层递推：

• 状态0：当前节点未被覆盖，需要父节点安装摄像头
• 状态1：当前节点已被覆盖，但自身没有安装摄像头
• 状态2：当前节点安装了摄像头

递推规则：

1. 如果任意一个直接子节点状态为0（未被覆盖），当前节点必须安装摄像头，答案计数+1，当前节点状态记为2
2. 如果任意一个直接子节点状态为2（安装了摄像头），当前节点已被覆盖，状态记为1
3. 其余情况当前节点状态记为0，等待父节点安装摄像头覆盖

所有层遍历完成后，如果根节点状态为0，需要额外给根节点安装1个摄像头。

保留BFS分层框架的修正代码如下：

class Solution
{
public:
    int minCameraCover(TreeNode *root)
    {
        if (!root) return 0;
        int ans = 0;
        queue<TreeNode*> q;
        q.push(root);
        vector<vector<TreeNode*>> levels;
        // 保留原代码的层序遍历逻辑，先存储每一层的节点
        while (!q.empty())
        {
            int sz = q.size();
            vector<TreeNode*> level;
            while (sz--)
            {
                TreeNode* cur = q.front();
                q.pop();
                level.push_back(cur);
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }
            levels.push_back(level);
        }
        unordered_map<TreeNode*, int> state; // 存储节点状态
        // 从最底层往根节点逐层递推
        for (int i = levels.size() - 1; i >= 0; --i)
        {
            for (TreeNode* node : levels[i])
            {
                bool needPlaceCam = false;
                // 子节点有未覆盖的，当前必须装摄像头
                if (node->left && state[node->left] == 0) needPlaceCam = true;
                if (node->right && state[node->right] == 0) needPlaceCam = true;
                if (needPlaceCam)
                {
                    ans++;
                    state[node] = 2;
                    continue;
                }
                // 子节点有摄像头，当前已经被覆盖
                bool coveredByChild = false;
                if (node->left && state[node->left] == 2) coveredByChild = true;
                if (node->right && state[node->right] == 2) coveredByChild = true;
                state[node] = coveredByChild ? 1 : 0;
            }
        }
        // 根节点未被覆盖的话需要补一个摄像头
        if (state[root] == 0) ans++;
        return ans;
    }
};

这个版本保留了你原来BFS分层遍历的代码结构，但已经抛弃了「奇偶层全装摄像头」的错误假设——后者本质是对题目覆盖规则的误判，不存在局部修改就能通过所有用例的可能。

内容的提问来源于stack exchange，提问作者Parminder Singh