LeetCode 题解工作台
监控二叉树
给定一个二叉树，我们在树的节点上安装摄像头。 节点上的每个摄影头都可以监视 其父对象、自身及其直接子对象。 计算监控树的所有节点所需的最小摄像头数量。 示例 1： 输入： [0,0,null,0,0] 输出： 1 解释： 如图所示，一台摄像头足以监控所有节点。 示例 2： 输入： [0,0,null…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 二分·树·traversal
答案摘要
对于每个节点，我们定义三种状态： - `a`：当前节点有摄像头
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1：
输入：[0,0,null,0,0] 输出：1 解释：如图所示，一台摄像头足以监控所有节点。
示例 2：
输入：[0,0,null,0,null,0,null,null,0] 输出：2 解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
提示：
- 给定树的节点数的范围是
[1, 1000]。 - 每个节点的值都是 0。
解题思路
方法一：动态规划（树形 DP）
对于每个节点，我们定义三种状态：
a：当前节点有摄像头b：当前节点无摄像头，但被子节点监控c：当前节点无摄像头，也没被子节点监控
接下来，我们设计一个函数 ，它将返回一个长度为 3 的数组，表示以 root 为根的子树中，三种状态下的最小摄像头数量。那么答案就是 。
函数 的计算过程如下：
如果 root 为空，则返回 ，其中 inf 表示一个很大的数，它用于表示不可能的情况。
否则，我们递归计算 root 的左右子树，分别得到 和 。
- 如果当前节点有摄像头，那么它的左右节点必须都是被监控的状态，即 。
- 如果当前节点无摄像头，但被子节点监控，那么子节点可以是其中之一或者两个都有摄像头，即 。
- 如果当前节点无摄像头，也没被子节点监控，那么子节点必须被其子节点监控，即 。
最后，我们返回 。
时间复杂度 ，空间复杂度 。其中 是二叉树的节点数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minCameraCover(self, root: Optional[TreeNode]) -> int:
def dfs(root):
if root is None:
return inf, 0, 0
la, lb, lc = dfs(root.left)
ra, rb, rc = dfs(root.right)
a = min(la, lb, lc) + min(ra, rb, rc) + 1
b = min(la + rb, lb + ra, la + ra)
c = lb + rb
return a, b, c
a, b, _ = dfs(root)
return min(a, b)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N) because each node is visited once. Space complexity is O(H) due to recursion stack, where H is the height of the tree. |
| 空间 | O(H) |
面试官常问的追问
外企场景- question_mark
Wants an optimal solution using DFS with minimal cameras
- question_mark
Interested in how you track node states during traversal
- question_mark
Checks if you handle edge cases like skewed or leaf-heavy trees
常见陷阱
外企场景- error
Placing cameras on every node instead of minimal set
- error
Failing to correctly propagate covered states from children
- error
Ignoring the coverage of parent nodes leading to overcounting cameras
进阶变体
外企场景- arrow_right_alt
Find minimum cameras in n-ary trees instead of binary trees
- arrow_right_alt
Compute camera placement when some nodes cannot hold cameras
- arrow_right_alt
Determine camera placement for dynamic trees that can change structure