968. Binary Tree Cameras 二叉树监控（贪心 + 树形 DP 状态机）题解
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
导读
本篇基于 LeetCode-Go 仓库中 968. Binary Tree Cameras 题解文档，完整讲解「二叉树监控」这道经典贪心/树形 DP 题：如何用最少的摄像头覆盖整棵二叉树的所有节点。文章先给出题目与核心思想，再结合仓库内 完整 Go 实现 与 单元测试 逐行剖析贪心染色法与三状态递归实现，最后给出测试运行与复杂度分析，帮助你彻底吃透这类“树上覆盖”问题的通用解法。
题目
给定一棵二叉树，在树的节点上安装摄像头。每个节点上的摄像头都可以监视其父节点、自身以及它的直接子节点。计算监控树中所有节点所需的最少摄像头数量。
示例 1：
输入：[0,0,null,0,0] 输出：1 解释：如图所示放置一个摄像头即可监控所有节点。示例 2：
输入：[0,0,null,0,null,0,null,null,0] 输出：2 解释：至少需要两个摄像头才能监控树的所有节点。上图展示了其中一种合法的摄像头放置方案。注意：
- 给定树的节点数范围为
[1, 1000]； - 每个节点的值都是 0（节点值本身对解题没有影响，仅为占位）。
题目大意
给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄像头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。
提示：
- 给定树的节点数的范围是 [1, 1000]。
- 每个节点的值都是 0。
解题思路
核心思想：贪心 + 节点三分类
给出一棵树，要求在这棵树上放置摄像头，一个摄像头最多可以监视 4 个节点：2 个孩子节点、节点本身、还有父节点。问最少放多少个摄像头可以覆盖树上的所有节点。
这一题可以用贪心思想来解。先将节点分为 3 类：
- 第一类（叶子节点，状态 0）：没有任何摄像头覆盖到，需要被父节点的摄像头覆盖，或者自己放摄像头；
- 第二类（包含叶子节点的节点，状态 1）：是某个放摄像头的节点的“父节点”，即它自己放了摄像头；
- 第三类（其中一个孩子已放摄像头、自身已被覆盖的节点，状态 2）：自身已被孩子的摄像头覆盖，不需要再放摄像头。
按照这个想法，将树的每个节点染色，如下图所示（图片出自原题解文档，用于直观展示贪心染色过程）。
贪心策略：从最底层叶子节点往上“染色”
所有包含叶子节点的节点，可以放一个摄像头，这个摄像头可以覆盖至少 3 个节点；如果还有父节点的话，可以覆盖 4 个节点。所以贪心的策略是从最下层的叶子节点开始往上“染色”：
- 先把最下面一层的叶子节点染成 1——标 1 的节点都是要放一个摄像头的；
- 如果某节点的孩子中包含 1（放了摄像头），那么再将该节点染成 2。如下图中的黄色节点——黄色节点代表不用放摄像头的节点，因为它已经被叶子节点的摄像头覆盖了；
- 出现了 2 的节点以后，再往上的节点又再次恢复成“叶子节点”0，需要继续被上层覆盖；
- 如此类推，直到推到根节点。
根节点收尾的边界情况
最后根节点还需要注意多种情况：
- 根节点可能是叶子节点 0，那么最终答案还需要+1，因为需要在根节点上放一个摄像头，否则根节点覆盖不到；
- 根节点也有可能是1 或者 2，这两种情况都不需要增加摄像头了，因为都已经覆盖到了。
按照上述方法，递归即可得到答案。
仓库源码逐行解析
仓库中该题目的完整实现位于 968. Binary Tree Cameras.go，文件开头的注释给出了 LeetCode 标准的二叉树节点定义（TreeNode类型通过 structures/TreeNode.go 复用）：
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */三状态定义
实现中用自定义类型status表达了上面解题思路里的三分类：
type status int const ( isLeaf status = iota // 0：叶子节点（未被覆盖，需要被上层照顾） parentofLeaf // 1：放了摄像头的节点 isMonitoredWithoutCamera // 2：已被孩子摄像头覆盖、无需再放摄像头 )三个常量值分别对应 0、1、2，与解题思路中的染色编号完全一致。
主函数与递归
func minCameraCover(root *TreeNode) int { res := 0 if minCameraCoverDFS(root, &res) == isLeaf { res++ } return res } func minCameraCoverDFS(root *TreeNode, res *int) status { if root == nil { return 2 } left, right := minCameraCoverDFS(root.Left, res), minCameraCoverDFS(root.Right, res) if left == isLeaf || right == isLeaf { *res++ return parentofLeaf } else if left == parentofLeaf || right == parentofLeaf { return isMonitoredWithoutCamera } else { return isLeaf } }递归逻辑对照贪心染色
- 空节点返回 2：
nil孩子相当于一个“已被覆盖、不需要摄像头”的节点，不会影响父节点的决策。注意这里2是数字字面量，等价于isMonitoredWithoutCamera。 - 孩子中有 0（叶子）：说明当前节点是“包含叶子节点的节点”，按贪心策略应当放一个摄像头（
res++），并向上返回1（parentofLeaf）。 - 孩子中有 1（放了摄像头）：当前节点已被孩子覆盖，不需要放摄像头，返回
2（isMonitoredWithoutCamera）。 - 否则（两个孩子都是 2）：当前节点没有任何覆盖来源，只能“寄希望于父节点”，向上返回
0（isLeaf）。 - 根节点收尾：递归结束后若根节点返回
0（叶子状态，没有被任何摄像头覆盖），则res++，在根节点补放一个摄像头。
该实现是一个典型的后序遍历（post-order DFS）：先递归处理左右子树，再根据两个孩子的状态决定当前节点的状态，正好对应“自底向上染色”的过程。每个节点只访问一次，空间复杂度为树高 O(H)。
单元测试与运行
仓库内配套测试位于 968. Binary Tree Cameras_test.go，覆盖了题目给出的两个官方示例，并额外补充了单节点树的边界用例：
输入（层序数组，structures.NULL表示空） | 期望输出 | 用例类型 |
|---|---|---|
[0,0,NULL,0,0] | 1 | 官方示例 1 |
[0,0,NULL,0,NULL,0,NULL,NULL,0] | 2 | 官方示例 2 |
[0] | 1 | 单节点边界 |
测试将层序数组通过 structures.Ints2TreeNode 构建二叉树后调用minCameraCover，并断言结果。structures.NULL定义于 structures/TreeNode.go，值为-1 << 63，用于在测试数据中表示空节点。
运行该用例（在仓库根目录执行）：
go test -v -run Test_Problem968 ./leetcode/0968.Binary-Tree-Cameras/输出示例：
------------------------Leetcode Problem 968------------------------ 【input】:[0 0 -9223372036854775808 0 0] 【output】:1 【input】:[0 0 -9223372036854775808 0 -9223372036854775808 0 -9223372036854775808 -9223372036854775808 0] 【output】:2 【input】:[0] 【output】:1提示：打印出来的
-9223372036854775808即为structures.NULL的真实数值（-1 << 63）。
若要跑全仓库测试并生成覆盖率报告，可参考仓库根目录的 gotest.sh：
go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...复杂度分析
- 时间复杂度：O(N)，N 为节点总数。后序遍历每个节点恰好访问一次，每个节点的决策均为 O(1)。
- 空间复杂度：O(H)，H 为树的高度。递归调用栈深度最坏情况下为 O(N)（退化成链状树），最好情况下为 O(log N)（平衡树）。
小结
968 题的核心套路可以总结为一句：后序遍历 + 三状态贪心。用 0/1/2 三个状态表达“需要被覆盖 / 自己放摄像头 / 已被覆盖”，自底向上决策，最后单独处理根节点。理解这一题后，同一套路也可迁移到其他“树上最小覆盖”类问题（如监控叶子、覆盖边等变体），是学习树形 DP 与贪心结合的良好入门案例。
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
