尧图网页设计 
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 } }递归逻辑对照贪心染色空节点返回 2nil孩子相当于一个“已被覆盖、不需要摄像头”的节点不会影响父节点的决策。注意这里2是数字字面量等价于isMonitoredWithoutCamera。孩子中有 0叶子说明当前节点是“包含叶子节点的节点”按贪心策略应当放一个摄像头res并向上返回1parentofLeaf。孩子中有 1放了摄像头当前节点已被孩子覆盖不需要放摄像头返回2isMonitoredWithoutCamera。否则两个孩子都是 2当前节点没有任何覆盖来源只能“寄希望于父节点”向上返回0isLeaf。根节点收尾递归结束后若根节点返回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.shgo test -covermodeatomic -coverprofilecoverage.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），仅供参考 968. Binary Tree Cameras 二叉树监控（贪心 + 树形 DP 状态机）题解
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 } }递归逻辑对照贪心染色空节点返回 2nil孩子相当于一个“已被覆盖、不需要摄像头”的节点不会影响父节点的决策。注意这里2是数字字面量等价于isMonitoredWithoutCamera。孩子中有 0叶子说明当前节点是“包含叶子节点的节点”按贪心策略应当放一个摄像头res并向上返回1parentofLeaf。孩子中有 1放了摄像头当前节点已被孩子覆盖不需要放摄像头返回2isMonitoredWithoutCamera。否则两个孩子都是 2当前节点没有任何覆盖来源只能“寄希望于父节点”向上返回0isLeaf。根节点收尾递归结束后若根节点返回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.shgo test -covermodeatomic -coverprofilecoverage.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），仅供参考