监控二叉树
# 📃 题目描述
题目链接:968. 监控二叉树 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定一个二叉树,我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1:
输入:[0,0,null,0,0]
输出:1
解释:如图所示,一台摄像头足以监控所有节点。
示例 2:
输入:[0,0,null,0,null,0,null,null,0]
输出:2
解释:需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
# 🔔 解题思路
重点:摄像头不要放在叶子节点上,摄像头可以覆盖上中下三层,如果把摄像头放在叶子节点上,就浪费的一层的覆盖。
⭐ 所以我们要从下往上看(后序遍历):
局部最优:让叶子节点的父节点安摄像头,所用摄像头最少;整体最优:全部摄像头数量所用最少
此时,大体思路就是从下到上,先给叶子节点父节点放个摄像头,然后隔一个节点放一个摄像头,直至到二叉树头结点。
此时这道题目还有两个难点:
- 二叉树如何从下往上遍历?(后序遍历,左右根)
- 如何隔一个节点放一个摄像头?
我们来列举下每个节点可能的状态:
有摄像头
没有摄像头,又分为:
2.1 被覆盖到
2.2 没有被覆盖到
所以实际上就是 3 个状态,我们可以用 3 个数字来表示:
【0】:没有被覆盖到
【1】:被覆盖到
【2】:有摄像头
那么突破点在哪里,也就是说这棵树的初始值该怎么设置?这些状态的判断肯定得有一个初始值才能运转起来对吧。
突破点就是空节点!
考虑下空节点的状态是什么?
没有被覆盖到?那不行,一个叶子节点对应两个空节点,要是空节点的状态是没有被覆盖到,那叶子节点就需要放摄像头了
有摄像头?那不行,依据题意,节点上的每个摄影头可以监视其父对象、自身及其直接子对象。空结点如果有摄像头的话,那么其父节点也就是叶子节点的状态就是被覆盖到,那么这个叶子节点的父节点就不会在放置摄像头了,显然不符合逻辑。
所以空节点的状态只能是被覆盖到,这样其父节点也就是叶子节点就不需要放置摄像头,而且也可以在这个叶子节点的父节点放置摄像头了
if (cur == null) { return 1 }
确定了突破口是空节点后,我们再来处理非叶子节点(记为 cur)的情况:
根据我们从下往上处理的后序遍历的逻辑,我们的目标就是要让 cur 的左右孩子都能被覆盖到!
左右孩子都有覆盖:说明左右孩子的孩子有摄像头,当然这个摄像头没法覆盖到 cur,所以 cur 应该就是无覆盖的状态了
if (cur.left == 1 && cur.right == 1) { return 0; }
左右孩子至少有一个无覆盖的情况:此时需要在 cur 节点处放置摄像头
if (cur.left == 0 || cur.right == 0) { res ++; // 摄像头数量 return 2; }
左右节点至少有一个有摄像头:此时 cur 节点被覆盖
if (cur.left == 2 || cur.right == 2) { return 1; }
如果左节点有摄像头【2】,右节点没摄像头并且也没被覆盖【0】怎么办呢?
这种情况在第 2 点已经判断过了
所有情况处理完之后,我们还需要判断下根节点是否被覆盖,若没有,则需要添加摄像头
class Solution {
// 摄像头数量
private int res = 0;
// 没有被覆盖到
private static int UNCOVERED = 0;
// 被覆盖到
private static int COVERED = 1;
// 有摄像机
private static int CAMERA = 2;
public int minCameraCover(TreeNode root) {
if (root == null) {
return 0;
}
// traversal(root) 返回的是 root 节点的状态
if (traversal(root) == UNCOVERED) {
res ++;
}
return res;
}
// 返回 cur 节点的状态
private int traversal(TreeNode cur) {
if (cur == null) {
return COVERED;
}
int left = traversal(cur.left);
int right = traversal(cur.right);
// 左右孩子都被覆盖
if (left == COVERED && right == COVERED) {
return UNCOVERED;
}
// 左右孩子至少有一个没被覆盖
if (left == UNCOVERED || right == UNCOVERED) {
res ++;
return CAMERA;
}
// 左右孩子至少有一个有摄像头
if (left == CAMERA || right == CAMERA) {
return COVERED;
}
// 不会走到这里
return -1;
}
}
# 💥 复杂度分析
- 空间复杂度:O(LogN)
- 时间复杂度:O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~