LeetCode·968.监控二叉树·贪心

链接：https://leetcode.cn/problems/binary-tree-cameras/solution/-by-xun-ge-v-gq66/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

 

示例

 

思路

解题思路
从题目中示例，其实可以得到启发，我们发现题目示例中的摄像头都没有放在叶子节点上！

这是很重要的一个线索，摄像头可以覆盖上中下三层，如果把摄像头放在叶子节点上，就浪费的一层的覆盖。

所以把摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。

那么有同学可能问了，为什么不从头结点开始看起呢，为啥要从叶子节点看呢？

因为头结点放不放摄像头也就省下一个摄像头， 叶子节点放不放摄像头省下了的摄像头数量是指数阶别的。

所以我们要从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！

局部最优推出全局最优，找不出反例，那么就按照贪心来！

此时，大体思路就是从低到上，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头结点。

对于任意一个节点来说有如下三种情况：

1. 该节点无覆盖
2. 本节点有摄像头
3. 本节点有覆盖

我们分别有三个数字来表示：

• 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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。