0%

每日一题 leetcode 968

给定一个二叉树,我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。

example1
example2

给定树的节点数的范围是 [1, 1000]。

思路:将每个节点的状态表示成三个数:0,1,2。0表示该节点未被覆盖,1表示该节点放置摄像头,2表示该节点被覆盖。那么空节点应该被设置成什么转态呢?为了让放置的摄像头的数量最少,应该不让叶节点防止摄像头,也就是在叶节点的父节点放置摄像头,空节点不能放摄像头所以不能是1,如果设成1说明叶节点可以放置摄像头,不符合,所以空节点的状态应该被设成2。所以有以下几个情况:
使用后序遍历:
1.左右孩子都被覆盖:
l=2 & r=2
说明该节点出于未覆盖状态。
2.左右孩子至少有一个没覆盖:
l=0 & r=0
l=0 & r=1
l=0 & r=2
l=1 & r=0
l=2 & r=0
3.左右孩子至少有一个摄像头:
l=1 & r=0
l=1 & r=1
l=1 & r=2
l=0 & r=1
l=2 & r=1
说明该节点被孩子节点的摄像头覆盖了
最后如果根节点如果没被覆盖要再加上一个摄像头。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
//0表示节点未被覆盖
//1表示节点放置摄像头
//2表示节点被覆盖
int res=0;
int minCameraCover(TreeNode* root) {
if(dfs(root)==0)res++;
return res;
}
int dfs(TreeNode *root){
if(!root)return 2;
int l=dfs(root->left);
int r=dfs(root->right);
//左右都被覆盖
if(l==2 && r==2) return 0;
//左右至少一个没覆盖
if(l==0 || r==0){
res++;
return 1;
}
//左右至少一个摄像头
if(l==1 || r==1) return 2;
return 0;
}
};