968. 监控二叉树
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
//后序遍历+贪心
int result;//记录摄像头个数
//0无覆盖 1有摄像头 2有覆盖
//1.确认返回类型和参数,通过返回值来判断左右孩子的状态
int traversal(TreeNode* root)
{
//2.中止条件，如果节点是空，那么该节点设置为有覆盖
//不然这个空节点的父节点（叶子节点）要放摄像头了
if(root == nullptr) return 2;
//3.每个节点的行为
//后序遍历，先获得左右孩子的状态
int left = traversal(root -> left);
int right = traversal(root -> right);
//两个孩子只要有其中一个没有被覆盖，那么该节点就要放置摄像头
if(left == 0 || right == 0)
{
result++;
return 1;//设置摄像头
}
//两个孩子只要有一个是有摄像头，那么该节点状态为被覆盖
else if(left == 1 || right == 1)
{
return 2;
}
return 0;//不放摄像头也没被覆盖，那就还是0
}
int minCameraCover(TreeNode* root) {
result = 0;
if(traversal(root) == 0) result++;
return result;
}
};
这道题，我跟代码随想录的思路是一样的，都是后序遍历+贪心，但我实在太贪，细节没处理好，只能通过部分样例，我没有写traversal函数，直接用原函数递归，结果就有特殊情况（只有一个根节点的时候），分开写后，加了特判，还是不行，原来还是有逻辑漏洞的。还是得根据左右孩子的状态来判断是否设置摄像头，而且特判情况是当根节点没有被覆盖时，都要+1，我之前自己写的特判是，当树只有一个节点时，才会+1，怪不得不能全部通过。
这是代码随想录里贪心章节的最后一题，正好是个困难，那今天就刷一道好了（偷个懒）。明天开动态规划章节，我看dp章节题目挺多的，大概刷一周就继续去刷PAT吧，备战浙大吧还是（还不知道能不能过夏令营初审呢）。