LeetCode 968. 监控二叉树
题目描述
题意分析
在二叉树的一些节点上安装摄像头，使所有实际节点都被监控，求最少需要多少个。一个摄像头只能覆盖自己、父节点和直接孩子，不能覆盖兄弟节点或更远的后代。
被其他摄像头覆盖的节点，并不会因此继续向外提供覆盖。判断父节点是否需要安装时，必须区分孩子“已经被覆盖”和“自己装有摄像头”，只记录一个是否覆盖的布尔值不够。
解法：后序贪心状态递归
核心思路
[!blue]
从叶子向根处理。定义返回状态时，当前节点的所有严格后代都已经处理并覆盖，只有当前节点自身可能需要父层帮助。三个状态分别是：
NEED_COVER表示当前节点还未覆盖；HAS_CAMERA表示当前节点已安装摄像头，能够覆盖父节点；COVERED表示当前节点被孩子覆盖，但自己没有摄像头，不能帮助父节点。如果任一孩子返回未覆盖，当前节点就安装摄像头。这个孩子的后代已经覆盖，新增设备是为了解决孩子本身；把这台设备放在当前父节点，可以同样覆盖它，还能覆盖父节点、另一孩子及更上一层。相比为未覆盖孩子单独放一台，并不会增加数量，也不会使已处理的后代失去覆盖，因此优先放在父层是安全的。
如果没有孩子未覆盖，但有孩子自己带摄像头，当前节点已经被它覆盖，无需再安装，返回
COVERED。如果两侧都已经覆盖却都没有摄像头，当前节点仍未覆盖；此时先不在这里安装，返回NEED_COVER，把选择留给父节点，以便利用更高位置的一台摄像头同时解决更多尚未处理的节点。必须先处理“存在未覆盖孩子”的情况。另一侧孩子上的摄像头只能覆盖它的父节点，无法横跨两条边覆盖兄弟，所以不能因为一侧有摄像头就忽略另一侧的需求。
空节点没有监控需求，视为
COVERED，也不提供摄像头。于是普通叶子会返回未覆盖，让父节点统一照顾；只有根没有父节点，遍历结束后若根仍未覆盖，就必须在根再补一台。后序先解决最深的未覆盖需求，并在不增加设备数的前提下尽量把设备放高；不被迫安装时则等待父层。这个局部选择可以替换对应的更低放置而不损失必要覆盖，因此逐层累计得到最少摄像头数。
解题步骤
- 初始化摄像头数量为零，后序递归求左右孩子的状态；空节点返回已覆盖。
- 任一孩子未覆盖时，数量加一，返回当前有摄像头。
- 否则若任一孩子有摄像头，返回当前已覆盖但无摄像头。
- 其余情况返回当前未覆盖，等待父节点处理。
- 最后检查根状态，若仍未覆盖再增加一台；Java 每次公开调用先重置计数。
代码实现
class Solution {
private static final int HAS_CAMERA = 0;
private static final int COVERED = 1;
private static final int NEED_COVER = 2;
private int cameras;
public int minCameraCover(TreeNode root) {
// 每次调用独立统计摄像头，不能沿用上次结果。
cameras = 0;
// 根没有父节点，必须自行补足覆盖。
if (dfs(root) == NEED_COVER) {
cameras++;
}
return cameras;
}
private int dfs(TreeNode node) {
if (node == null) {
return COVERED;
}
int left = dfs(node.left);
int right = dfs(node.right);
// 先满足未覆盖的孩子，另一侧摄像头不能代替当前节点。
if (left == NEED_COVER || right == NEED_COVER) {
cameras++;
return HAS_CAMERA;
}
if (left == HAS_CAMERA || right == HAS_CAMERA) {
return COVERED;
}
// 孩子都已覆盖但无摄像头，当前节点留给父层。
return NEED_COVER;
}
}
func minCameraCover(root *TreeNode) int {
const (
hasCamera = 0
covered = 1
needCover = 2
)
cameras := 0
var dfs func(node *TreeNode) int
dfs = func(node *TreeNode) int {
if node == nil {
return covered
}
left := dfs(node.Left)
right := dfs(node.Right)
// 先满足未覆盖的孩子，另一侧摄像头不能代替当前节点。
if left == needCover || right == needCover {
cameras++
return hasCamera
}
if left == hasCamera || right == hasCamera {
return covered
}
// 孩子都已覆盖但无摄像头，当前节点留给父层。
return needCover
}
// 根没有父节点，必须自行补足覆盖。
if dfs(root) == needCover {
cameras++
}
return cameras
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点后序访问一次，只根据两个孩子的状态做常量判断。
- 空间复杂度：$O(h)$，保存高度为
h的递归调用栈，最坏为 $O(n)$。
关键点总结
[!green]
- 返回状态只描述当前节点，严格后代的监控需求已经处理完毕。
- 未覆盖孩子要求优先响应，一个父节点的摄像头可以同时满足两个孩子的需求。
- 已覆盖不等于拥有摄像头，只有后者能够继续覆盖父节点。
- 根没有父层可等待，必须在递归结束后单独补足。
易错点总结
[!yellow]
- 先判断有摄像头的孩子，会掩盖另一侧未覆盖孩子的需求，误以为兄弟之间可以互相覆盖。
- 把空节点设为未覆盖，会迫使叶子安装并不需要的摄像头。
- 将已覆盖无摄像头和有摄像头合并成一种状态，父层无法判断自己是否被覆盖。
- 忘记根的最后检查，会让需要父层帮助的根始终漏监控，单节点树尤其明显。
- Java 复用对象时不重置成员计数，会把前一次调用的结果带入新计算。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 337. 打家劫舍 III | 中等 | 同样后序决定节点是否放置设备或被选择，本题还必须区分已覆盖与等待父节点覆盖的状态。 |