怀疑女朋友劈腿了，她最近手机总是静音，洗澡都要带着。昨天我偷偷定位她，发现她居然在高级酒店！

监控二叉树这个算法题其实就是变着法让你练“后序遍历”+“状态DP”，就看你会不会装监控器了，代码不是关键，思路才是王道。

先说下题目大意：

有一棵二叉树，每个节点你可以选择装或者不装监控器。每个监控器可以监控自身、父节点、左右孩子。问最少需要几个监控器，能覆盖整棵树。

我看到这题的第一反应就是——这不就是在问“你家装几个摄像头能防小偷”，而且摄像头还能看隔壁，简直是小区安防协会内部考核题目 😅。

回到正题，这种题一看就是树形DP的经典题型，我们要干的其实很简单——给每个节点打三个状态标签：

finalintNOT_COVERED=0; // 本节点没被监控
finalintHAS_CAMERA=1;  // 本节点有摄像头
finalintCOVERED=2;     // 本节点被监控（但自己没摄像头）

核心套路是后序遍历，先处理完左子树和右子树，然后再决定当前节点该干嘛。这个时候你会发现，人生和树真的很像，都是“你以为你自己不重要，其实你子女不行你也就完蛋了”。

我们直接上代码看一遍思路：

classSolution {
intcameras=0;

publicintminCameraCover(TreeNode root) {
if (dfs(root) == NOT_COVERED) {
            cameras++; // 根节点如果没被覆盖，那只能在根上装一个
        }
return cameras;
    }

privateintdfs(TreeNode node) {
if (node == null) return COVERED; // 空节点默认是被覆盖的

intleft= dfs(node.left);
intright= dfs(node.right);

if (left == NOT_COVERED || right == NOT_COVERED) {
// 子节点有没被覆盖的，那我得装个摄像头
            cameras++;
return HAS_CAMERA;
        }

if (left == HAS_CAMERA || right == HAS_CAMERA) {
// 子节点有摄像头，我被覆盖了
return COVERED;
        }

// 两个子节点都被覆盖了，但是没摄像头，那我自己还没被覆盖
return NOT_COVERED;
    }
}

整个代码就这么点，但是逻辑非常缜密，关键在于理解三种状态之间的关系。这里稍微扩展一下，避免大家掉坑里：

• • 很多人在写完第一遍的时候，容易写出“贪心型的逻辑”，比如哪里没被覆盖就马上放一个摄像头。这样其实会导致摄像头数量多，因为你没有把“能覆盖多的就优先装”这个贪心原则做对。
• • 所以真正的精髓是：让叶子的父节点装摄像头，而不是叶子自己装。

这点非常像项目管理——干活的程序员不重要，关键是你得给带他们的Leader配好电脑😎。

我一开始刷这题时还有个误区，想着用个Map<TreeNode, Integer>来记状态，结果代码冗余到不忍直视。后来才发现，三种状态值足以表达所有情况，根本不用标记整个节点结构，轻装上阵才是刷题的艺术。

有人会问，如果这题改成“摄像头只能看左右子节点”怎么办？我只能说，那就是另一道题了，DP方程直接得重写。这题的精髓就是利用“摄像头能看父节点”这一点做文章，如果你一味乱放，那最后根节点又要补装一次。

我刷完这题之后感悟特别深：算法的优雅，体现在你把混乱的逻辑归纳为几个固定状态，然后用一个遍历就能算出全局最优。

而且写完之后你会发现，这题就是典型的“写一遍就懂，过两天就忘”类型。建议记住三种状态，未来刷树题看到“局部装置影响全局”的场景，就能立马想到用这种状态压缩思路。

最后吐槽一句，有时候我写代码就像装摄像头，一堆地方需要覆盖，每次都想着“这里加个try-catch吧”、“那边加个日志吧”，结果一堆“摄像头”，可就是bug还是找不到。😂

你刷这题了吗？或者你觉得现实中有没有遇到那种“左边有坑，右边也不省心，最后只能我自己上”的场景？欢迎评论区晒一下，看看到底谁最惨。