LeetCode·968.监控二叉树·贪心
2023-09-27 14:26:29 时间
链接:https://leetcode.cn/problems/binary-tree-cameras/solution/-by-xun-ge-v-gq66/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
题目
示例
思路
解题思路
从题目中示例,其实可以得到启发,我们发现题目示例中的摄像头都没有放在叶子节点上!
这是很重要的一个线索,摄像头可以覆盖上中下三层,如果把摄像头放在叶子节点上,就浪费的一层的覆盖。
所以把摄像头放在叶子节点的父节点位置,才能充分利用摄像头的覆盖面积。
那么有同学可能问了,为什么不从头结点开始看起呢,为啥要从叶子节点看呢?
因为头结点放不放摄像头也就省下一个摄像头, 叶子节点放不放摄像头省下了的摄像头数量是指数阶别的。
所以我们要从下往上看,局部最优:让叶子节点的父节点安摄像头,所用摄像头最少,整体最优:全部摄像头数量所用最少!
局部最优推出全局最优,找不出反例,那么就按照贪心来!
此时,大体思路就是从低到上,先给叶子节点父节点放个摄像头,然后隔两个节点放一个摄像头,直至到二叉树头结点。
对于任意一个节点来说有如下三种情况:
- 该节点无覆盖
- 本节点有摄像头
- 本节点有覆盖
我们分别有三个数字来表示:
- 0:该节点无覆盖
- 1:本节点有摄像头
- 2:本节点有覆盖
具体实现看代码,注释超级详细
代码
【未精简】
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int dfs(struct TreeNode * root, int * returnSize)
{
// 空节点,该节点有覆盖
if (root == NULL) return 2;
int left = dfs(root->left, returnSize); // 左
int right = dfs(root->right, returnSize); // 右
// 情况1
// 左右节点都有覆盖
if (left == 2 && right == 2) return 0;
// 情况2
// left == 0 && right == 0 左右节点无覆盖
// left == 1 && right == 0 左节点有摄像头,右节点无覆盖
// left == 0 && right == 1 左节点有无覆盖,右节点摄像头
// left == 0 && right == 2 左节点无覆盖,右节点覆盖
// left == 2 && right == 0 左节点覆盖,右节点无覆盖
if (left == 0 || right == 0) {
(*returnSize)++;
return 1;
}
// 情况3
// left == 1 && right == 2 左节点有摄像头,右节点有覆盖
// left == 2 && right == 1 左节点有覆盖,右节点有摄像头
// left == 1 && right == 1 左右节点都有摄像头
// 其他情况前段代码均已覆盖
if (left == 1 || right == 1) return 2;
// 这个 return -1 逻辑不会走到这里。
return -1;
}
int minCameraCover(struct TreeNode* root){
int returnSize = 0;
if(dfs(root, &returnSize) == 0)
returnSize++;
return returnSize;
}
作者:xun-ge-v
链接:https://leetcode.cn/problems/binary-tree-cameras/solution/-by-xun-ge-v-gq66/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
【精简版】
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int dfs(struct TreeNode * root, int * returnSize)
{
if(root == NULL) return 2;
int left = dfs(root->left, returnSize);
int right = dfs(root->right, returnSize);
if (left == 2 && right == 2) return 0;
else if (left == 0 || right == 0) {
(*returnSize)++;
return 1;
} else return 2;
}
int minCameraCover(struct TreeNode* root){
int returnSize = 0;
if(dfs(root, &returnSize) == 0)
returnSize++;
return returnSize;
}
作者:xun-ge-v
链接:https://leetcode.cn/problems/binary-tree-cameras/solution/-by-xun-ge-v-gq66/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相关文章
- Leetcode: Data Stream as Disjoint Intervals && Summary of TreeMap
- Leetcode: Graph Valid Tree && Summary: Detect cycle in undirected graph
- Leetcode: Unique Paths II
- JS leetcode 有序数组的平方 题解分析,灵活运用Math.pow与Math.abs方法
- [LeetCode] Max Points on a Line
- [LeetCode] Maximal Rectangle
- [LeetCode] 1053. Previous Permutation With One Swap 交换一次的先前全排列
- [LeetCode] 981. Time Based Key-Value Store 基于时间的键值存储
- [LeetCode] Max Area of Island 岛的最大面积
- [LeetCode] Minimum Index Sum of Two Lists 两个表单的最小坐标和
- [LeetCode] Find the Closest Palindrome 寻找最近的回文串