Screen驱动电源管理机制快速理解
2026/1/1 1:15:32
哈喽各位，我是前端小L。
欢迎来到贪心算法专题的大结局！ 题目背景很简单：给定一棵二叉树，我们在节点上安装摄像头。
一个摄像头可以监控它自己、它的父节点、它的子节点。
目标：计算监控整棵树所需的最少摄像头数量。
力扣 968. 监控二叉树
https://leetcode.cn/problems/binary-tree-cameras
题目分析：
输入：二叉树的根节点
root。输出：摄像头的最小数量。
核心思维：自底向上的贪心
直觉问题：摄像头放在哪最划算？
如果放在叶子节点：它只能监控自己和父节点（最多 2 个）。
如果放在叶子节点的父节点：它可以监控父节点、自己、两个子节点（最多 4 个）。
贪心策略：绝对不要把摄像头放在叶子节点上！这样太浪费了。 我们要让叶子节点的父节点去放摄像头，这样能“以此保三”（保住父、自、子）。
既然要从叶子节点开始考虑，那我们的遍历顺序必须是后序遍历（左右根），即自底向上推导。
状态定义：每个节点可能有三种状态（我们需要用数字标记）：
0：无覆盖(该节点没被监控，等着别人来救它)。
1：有摄像头(该节点自己装了摄像头)。
2：有覆盖(该节点被监控了，但不是自己装的，是被子节点或父节点照亮的)。
状态转移逻辑（核心）：对于当前节点，我们检查它的左右孩子：
情况一：左右孩子都有覆盖 (State 2)
孩子都安全了，那当前节点需要装摄像头吗？
不需要。为了贪心（省摄像头），当前节点最好别装，等着它的父节点装摄像头来监控它。
所以当前节点状态设为0 (无覆盖)。
情况二：左右孩子至少有一个无覆盖 (State 0)
只要有一个孩子在呼救，当前节点作为父亲，必须挺身而出！
必须装摄像头。
cameras++。当前节点状态设为1 (有摄像头)。
情况三：左右孩子至少有一个有摄像头 (State 1)
孩子里有摄像头，那当前节点就被孩子照亮了。
当前节点安全了。
当前节点状态设为2 (有覆盖)。
特殊情况：根节点
遍历结束后，如果根节点状态是 0（无覆盖），因为根节点没有父节点了，没人能救它。
必须给根节点补一个摄像头。
算法流程 (JavaScript)
定义结果变量
res = 0。定义递归函数
traversal(node)：终止条件：如果
node为空，返回什么状态？空节点不能是“无覆盖”，否则叶子节点会为了救空节点而装摄像头（浪费）。
空节点也不能是“有摄像头”。
空节点应该视为“有覆盖” (2)。这样叶子节点看到空孩子是 2，自己就会变成 0（等着父节点来救），符合贪心策略。
递归：
left = traversal(node.left)right = traversal(node.right)
逻辑判断：
if (left == 0 || right == 0) -> 装摄像头，
res++，返回 1。if (left == 1 || right == 1) -> 被覆盖，返回 2。
if (left == 2 && right == 2) -> 无覆盖，返回 0。
主函数：
调用
traversal(root)。检查返回值，如果 root 也是 0，
res++。返回
res。
代码实现
深度辨析：为什么顺序不能乱？
在代码中，判断顺序非常关键：
先判0 (无覆盖)：救人要紧。只要有孩子没被覆盖，必须装摄像头。
再判1 (有摄像头)：如果没人求救，但有孩子有摄像头，我就蹭个光。
最后默认：孩子都安全，我就先“躺平”（状态 0）。
如果你把判断顺序搞乱了，比如先判断有没有被覆盖，可能会导致在需要装摄像头的时候没装，破坏了覆盖结构。
总结：贪心算法毕业典礼
恭喜你！坚持到了这里。 这道题融合了树的遍历、状态机、局部贪心，是当之无愧的贪心压轴题。
回顾我们的贪心之旅：
基础：分发饼干（排序+匹配）。
序列：摆动序列（视觉上的峰谷）。
股票：买卖股票 II（收集每一滴利润）。
覆盖：跳跃游戏 I & II（维护最大范围）。
维度：分发糖果、重建队列（拆分维度，逐个击破）。
区间：射气球、无重叠、合并区间（Start排序 + 边界更新，这是最重要的模板！）。
数字：单调递增数字（借位思想）。
树形：监控二叉树（自底向上状态推导）。
掌握了这些，你已经建立了一套完整的**“贪心直觉”。在未来的面试中，当你面对一个“求最值”的问题，如果 DP 太复杂，不妨先问问自己：“如果我只顾眼前，能不能推导出全局最优？”**