1. 监控二叉树问题解析监控二叉树这道题乍看简单实则暗藏玄机。题目要求我们在二叉树的节点上放置摄像头使得每个节点都能被监控到即每个节点要么有摄像头要么被其父节点或子节点的摄像头覆盖同时使用尽可能少的摄像头。1.1 问题难点剖析这道题之所以被标记为困难主要因为以下几个挑战树形结构的特殊性二叉树不像数组或链表那样线性需要考虑父子节点之间的双向影响。一个节点的状态会同时影响其父节点和子节点的决策。状态依赖关系每个节点的最优解依赖于其子节点的状态而子节点的状态又可能反过来影响父节点的决策。这种相互依赖关系使得问题变得复杂。贪心算法的陷阱直觉上可能会想从根节点或叶子节点开始贪心地放置摄像头但实际测试会发现这种策略无法保证全局最优。1.2 解题思路选择经过多次尝试和思考我发现这个问题最适合采用后序遍历状态机的方法来解决。具体思路如下定义三种状态状态0该节点未被覆盖状态1该节点被覆盖但没有摄像头状态2该节点有摄像头递归处理子树从叶子节点开始向上处理每个节点根据其左右子树的状态来决定自身的最优状态。状态转移方程精心设计状态转移逻辑确保每个状态的计算都考虑到所有可能的情况。2. 算法实现详解2.1 状态定义与初始化在Go实现中我们用一个长度为3的slice来表示每个节点的三种状态// 返回的slice含义 // [0]该节点未被覆盖时的最小摄像头数 // [1]该节点被覆盖但没有摄像头时的最小摄像头数 // [2]该节点有摄像头时的最小摄像头数对于空节点nil我们这样初始化if root nil { return []int{0, 0, 10000} }这里用10000表示一个极大值因为空节点不可能放置摄像头所以状态2有摄像头应该被排除在选择之外。2.2 核心递归逻辑递归函数dfs的核心逻辑分为三部分状态0当前节点未被覆盖s0 : l[1] r[1]这意味着左右子节点必须处于状态1被覆盖但没有摄像头因为如果子节点有摄像头状态2当前节点就会被覆盖如果子节点未被覆盖状态0那么它们需要被自己的子节点覆盖这与当前状态定义矛盾。状态1当前节点被覆盖但没有摄像头s1 : min( l[2] min(r[2], r[1]), r[2] min(l[2], l[1]), )这种情况稍微复杂些。当前节点被覆盖意味着至少有一个子节点有摄像头状态2。我们有两种选择左子节点有摄像头右子节点可以是状态1或2右子节点有摄像头左子节点可以是状态1或2 我们取这两种情况的最小值。状态2当前节点有摄像头s2 : min3(l[0], l[1], l[2]) min3(r[0], r[1], r[2]) 1无论子节点处于什么状态当前节点都能覆盖它们。我们取左右子树所有状态的最小值之和然后加1当前节点的摄像头。2.3 辅助函数实现代码中使用了两个辅助函数func min(a, b int) int { if a b { return b } return a } func min3(a, b, c int) int { return min(a, min(b, c)) }这些简单的工具函数让主逻辑更加清晰易读。3. 算法正确性证明3.1 边界条件处理空节点处理空节点返回[0,0,10000]确保了它不会被选择作为摄像头放置点同时不影响父节点的状态计算。叶子节点处理对于叶子节点其左右子节点都是nil状态计算如下s0 0 0 0s1 min(10000min(10000,0), 10000min(10000,0)) 10000s2 min3(0,0,10000) min3(0,0,10000) 1 1这意味着对于叶子节点如果不放摄像头最优选择是让父节点来覆盖它状态0如果必须覆盖它放置摄像头是最优解状态23.2 状态转移的正确性通过数学归纳法可以证明这种状态转移的正确性基本情况对于叶子节点如上所述状态转移是正确的。归纳假设假设对于高度为h的子树状态转移是正确的。归纳步骤对于高度为h1的树其子节点高度为h根据归纳假设子节点的状态计算是正确的。当前节点的三种状态都基于子节点的正确状态进行计算因此也是正确的。4. 复杂度分析4.1 时间复杂度算法对每个节点只访问一次每次访问执行常数时间的操作因此时间复杂度为O(n)其中n是树中的节点数。4.2 空间复杂度空间复杂度主要来自递归调用栈。在最坏情况下树退化为链表递归深度为O(n)。此外算法只使用了常数大小的额外空间存储状态因此总空间复杂度为O(n)。5. 实际应用与变种5.1 实际问题中的应用这种监控二叉树的问题在实际中有很多应用场景网络安全监控在计算机网络中路由器可以看作节点放置监控设备类似于放置摄像头。城市安防系统在街道交叉口布置监控摄像头确保每个路口都被覆盖。无线传感器网络布置最少数量的传感器来监控整个区域。5.2 问题变种思考带权重的监控问题如果不同节点放置摄像头的成本不同如何最小化总成本多级监控要求每个节点被至少k个摄像头监控如何解决有向图监控将二叉树推广到一般的有向图问题会变得更加复杂。6. 常见错误与调试技巧6.1 常见错误类型贪心算法陷阱试图从根节点或叶子节点开始贪心地放置摄像头这样通常无法得到全局最优解。状态定义不全只考虑节点是否有摄像头而忽略了被覆盖但没有摄像头的状态导致无法正确处理某些情况。边界条件处理不当特别是对空节点的处理如果初始化值设置不当会影响整个计算结果。6.2 调试技巧小规模测试先用手工计算小树如3-5个节点的预期结果与程序输出对比。打印中间状态在递归函数中添加打印语句输出每个节点的状态值帮助理解状态转移过程。可视化工具使用二叉树可视化工具将实际监控方案绘制出来直观检查是否正确。7. 算法优化与比较7.1 与其他方法的比较暴力搜索法尝试所有可能的摄像头组合时间复杂度为O(2^n)完全不实用。动态规划法本文的方法本质上是一种树形DP相比暴力搜索效率大大提高。贪心算法虽然某些情况下能得到不错的结果但不能保证全局最优。7.2 可能的优化方向迭代实现将递归改为迭代使用显式栈来避免递归调用的开销。记忆化虽然在这个问题中每个节点只访问一次不需要额外记忆化但在更复杂的问题中可以考虑。并行计算对于非常大的树可以考虑并行处理不同的子树。8. 个人实现心得在实际编码过程中我最初尝试了从叶子节点开始贪心地放置摄像头但很快发现这种方法在某些情况下会多放置摄像头。经过多次调试和思考才确定了现在的状态定义和转移方程。有几个关键点值得注意状态定义要完备最初我只考虑了有摄像头和无摄像头两种状态忽略了被覆盖但无摄像头这个中间状态导致无法正确处理某些情况。空节点的处理要谨慎空节点的状态初始化值会直接影响整个计算过程需要仔细考虑。从简单案例入手先手工计算几个小例子确保理解正确后再编码可以节省大量调试时间。这种树形DP问题在LeetCode中并不少见掌握这类问题的解题模式对提高算法能力很有帮助。核心思想是定义合适的状态然后通过递归或迭代的方式计算每个节点的状态值最终得到全局最优解。 
长河君 · 2026/11/5 0:41:48 · 阅读 1.2k 二叉树监控问题：后序遍历与状态机解法详解
1. 监控二叉树问题解析监控二叉树这道题乍看简单实则暗藏玄机。题目要求我们在二叉树的节点上放置摄像头使得每个节点都能被监控到即每个节点要么有摄像头要么被其父节点或子节点的摄像头覆盖同时使用尽可能少的摄像头。1.1 问题难点剖析这道题之所以被标记为困难主要因为以下几个挑战树形结构的特殊性二叉树不像数组或链表那样线性需要考虑父子节点之间的双向影响。一个节点的状态会同时影响其父节点和子节点的决策。状态依赖关系每个节点的最优解依赖于其子节点的状态而子节点的状态又可能反过来影响父节点的决策。这种相互依赖关系使得问题变得复杂。贪心算法的陷阱直觉上可能会想从根节点或叶子节点开始贪心地放置摄像头但实际测试会发现这种策略无法保证全局最优。1.2 解题思路选择经过多次尝试和思考我发现这个问题最适合采用后序遍历状态机的方法来解决。具体思路如下定义三种状态状态0该节点未被覆盖状态1该节点被覆盖但没有摄像头状态2该节点有摄像头递归处理子树从叶子节点开始向上处理每个节点根据其左右子树的状态来决定自身的最优状态。状态转移方程精心设计状态转移逻辑确保每个状态的计算都考虑到所有可能的情况。2. 算法实现详解2.1 状态定义与初始化在Go实现中我们用一个长度为3的slice来表示每个节点的三种状态// 返回的slice含义 // [0]该节点未被覆盖时的最小摄像头数 // [1]该节点被覆盖但没有摄像头时的最小摄像头数 // [2]该节点有摄像头时的最小摄像头数对于空节点nil我们这样初始化if root nil { return []int{0, 0, 10000} }这里用10000表示一个极大值因为空节点不可能放置摄像头所以状态2有摄像头应该被排除在选择之外。2.2 核心递归逻辑递归函数dfs的核心逻辑分为三部分状态0当前节点未被覆盖s0 : l[1] r[1]这意味着左右子节点必须处于状态1被覆盖但没有摄像头因为如果子节点有摄像头状态2当前节点就会被覆盖如果子节点未被覆盖状态0那么它们需要被自己的子节点覆盖这与当前状态定义矛盾。状态1当前节点被覆盖但没有摄像头s1 : min( l[2] min(r[2], r[1]), r[2] min(l[2], l[1]), )这种情况稍微复杂些。当前节点被覆盖意味着至少有一个子节点有摄像头状态2。我们有两种选择左子节点有摄像头右子节点可以是状态1或2右子节点有摄像头左子节点可以是状态1或2 我们取这两种情况的最小值。状态2当前节点有摄像头s2 : min3(l[0], l[1], l[2]) min3(r[0], r[1], r[2]) 1无论子节点处于什么状态当前节点都能覆盖它们。我们取左右子树所有状态的最小值之和然后加1当前节点的摄像头。2.3 辅助函数实现代码中使用了两个辅助函数func min(a, b int) int { if a b { return b } return a } func min3(a, b, c int) int { return min(a, min(b, c)) }这些简单的工具函数让主逻辑更加清晰易读。3. 算法正确性证明3.1 边界条件处理空节点处理空节点返回[0,0,10000]确保了它不会被选择作为摄像头放置点同时不影响父节点的状态计算。叶子节点处理对于叶子节点其左右子节点都是nil状态计算如下s0 0 0 0s1 min(10000min(10000,0), 10000min(10000,0)) 10000s2 min3(0,0,10000) min3(0,0,10000) 1 1这意味着对于叶子节点如果不放摄像头最优选择是让父节点来覆盖它状态0如果必须覆盖它放置摄像头是最优解状态23.2 状态转移的正确性通过数学归纳法可以证明这种状态转移的正确性基本情况对于叶子节点如上所述状态转移是正确的。归纳假设假设对于高度为h的子树状态转移是正确的。归纳步骤对于高度为h1的树其子节点高度为h根据归纳假设子节点的状态计算是正确的。当前节点的三种状态都基于子节点的正确状态进行计算因此也是正确的。4. 复杂度分析4.1 时间复杂度算法对每个节点只访问一次每次访问执行常数时间的操作因此时间复杂度为O(n)其中n是树中的节点数。4.2 空间复杂度空间复杂度主要来自递归调用栈。在最坏情况下树退化为链表递归深度为O(n)。此外算法只使用了常数大小的额外空间存储状态因此总空间复杂度为O(n)。5. 实际应用与变种5.1 实际问题中的应用这种监控二叉树的问题在实际中有很多应用场景网络安全监控在计算机网络中路由器可以看作节点放置监控设备类似于放置摄像头。城市安防系统在街道交叉口布置监控摄像头确保每个路口都被覆盖。无线传感器网络布置最少数量的传感器来监控整个区域。5.2 问题变种思考带权重的监控问题如果不同节点放置摄像头的成本不同如何最小化总成本多级监控要求每个节点被至少k个摄像头监控如何解决有向图监控将二叉树推广到一般的有向图问题会变得更加复杂。6. 常见错误与调试技巧6.1 常见错误类型贪心算法陷阱试图从根节点或叶子节点开始贪心地放置摄像头这样通常无法得到全局最优解。状态定义不全只考虑节点是否有摄像头而忽略了被覆盖但没有摄像头的状态导致无法正确处理某些情况。边界条件处理不当特别是对空节点的处理如果初始化值设置不当会影响整个计算结果。6.2 调试技巧小规模测试先用手工计算小树如3-5个节点的预期结果与程序输出对比。打印中间状态在递归函数中添加打印语句输出每个节点的状态值帮助理解状态转移过程。可视化工具使用二叉树可视化工具将实际监控方案绘制出来直观检查是否正确。7. 算法优化与比较7.1 与其他方法的比较暴力搜索法尝试所有可能的摄像头组合时间复杂度为O(2^n)完全不实用。动态规划法本文的方法本质上是一种树形DP相比暴力搜索效率大大提高。贪心算法虽然某些情况下能得到不错的结果但不能保证全局最优。7.2 可能的优化方向迭代实现将递归改为迭代使用显式栈来避免递归调用的开销。记忆化虽然在这个问题中每个节点只访问一次不需要额外记忆化但在更复杂的问题中可以考虑。并行计算对于非常大的树可以考虑并行处理不同的子树。8. 个人实现心得在实际编码过程中我最初尝试了从叶子节点开始贪心地放置摄像头但很快发现这种方法在某些情况下会多放置摄像头。经过多次调试和思考才确定了现在的状态定义和转移方程。有几个关键点值得注意状态定义要完备最初我只考虑了有摄像头和无摄像头两种状态忽略了被覆盖但无摄像头这个中间状态导致无法正确处理某些情况。空节点的处理要谨慎空节点的状态初始化值会直接影响整个计算过程需要仔细考虑。从简单案例入手先手工计算几个小例子确保理解正确后再编码可以节省大量调试时间。这种树形DP问题在LeetCode中并不少见掌握这类问题的解题模式对提高算法能力很有帮助。核心思想是定义合适的状态然后通过递归或迭代的方式计算每个节点的状态值最终得到全局最优解。