CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

  • 数组

  • 链表

  • 哈希表

  • 字符串

  • 栈

  • 队列

  • 二叉树

  • 前缀树

  • 二分查找

  • 双指针法

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

    • 贪心算法理论基础
    • 找零
    • 柠檬水找零
    • 分发饼干
    • K 次取反后最大化的数组和
    • 加油站
    • 分发糖果
    • 根据身高重建队列
    • 划分字母区间
    • 单调递增的数字
    • 监控二叉树
      • 📃 题目描述
      • 🔔 解题思路
      • 💥 复杂度分析
    • 使数组变成交替数组的最少操作数
    • 剑指 Offer 14- II - 剪绳子 II
    • 区间调度问题

  • 动态规划

  • 图

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 贪心算法
小牛肉
2022-03-20
目录

监控二叉树

# 📃 题目描述

题目链接:968. 监控二叉树 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)

给定一个二叉树,我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

示例 1:

img

输入:[0,0,null,0,0]
输出:1
解释:如图所示,一台摄像头足以监控所有节点。

示例 2:

img

输入:[0,0,null,0,null,0,null,null,0]
输出:2
解释:需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

# 🔔 解题思路

重点:摄像头不要放在叶子节点上,摄像头可以覆盖上中下三层,如果把摄像头放在叶子节点上,就浪费的一层的覆盖。

⭐ 所以我们要从下往上看(后序遍历):

局部最优:让叶子节点的父节点安摄像头,所用摄像头最少;整体最优:全部摄像头数量所用最少

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

此时这道题目还有两个难点:

  1. 二叉树如何从下往上遍历?(后序遍历,左右根)
  2. 如何隔一个节点放一个摄像头?

我们来列举下每个节点可能的状态:

  1. 有摄像头

  2. 没有摄像头,又分为:

    2.1 被覆盖到

    2.2 没有被覆盖到

所以实际上就是 3 个状态,我们可以用 3 个数字来表示:

【0】:没有被覆盖到

【1】:被覆盖到

【2】:有摄像头

那么突破点在哪里,也就是说这棵树的初始值该怎么设置?这些状态的判断肯定得有一个初始值才能运转起来对吧。

突破点就是空节点!

考虑下空节点的状态是什么?

  • 没有被覆盖到?那不行,一个叶子节点对应两个空节点,要是空节点的状态是没有被覆盖到,那叶子节点就需要放摄像头了

  • 有摄像头?那不行,依据题意,节点上的每个摄影头可以监视其父对象、自身及其直接子对象。空结点如果有摄像头的话,那么其父节点也就是叶子节点的状态就是被覆盖到,那么这个叶子节点的父节点就不会在放置摄像头了,显然不符合逻辑。

  • 所以空节点的状态只能是被覆盖到,这样其父节点也就是叶子节点就不需要放置摄像头,而且也可以在这个叶子节点的父节点放置摄像头了

    if (cur == null) {
    	return 1
    }
    

确定了突破口是空节点后,我们再来处理非叶子节点(记为 cur)的情况:

根据我们从下往上处理的后序遍历的逻辑,我们的目标就是要让 cur 的左右孩子都能被覆盖到!

  1. 左右孩子都有覆盖:说明左右孩子的孩子有摄像头,当然这个摄像头没法覆盖到 cur,所以 cur 应该就是无覆盖的状态了

    if (cur.left == 1 && cur.right == 1) {
    	return 0;
    }
    
  2. 左右孩子至少有一个无覆盖的情况:此时需要在 cur 节点处放置摄像头

    if (cur.left == 0 || cur.right == 0) {
        res ++; // 摄像头数量
        return 2;
    }
    
  3. 左右节点至少有一个有摄像头:此时 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)

🎁 公众号

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

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
单调递增的数字
使数组变成交替数组的最少操作数

← 单调递增的数字 使数组变成交替数组的最少操作数→

最近更新
01
我掏出这个多线程轮子,面试官直接全体起立
04-13
02
面试官问你有其他 Offer 吗,该怎样回答
04-10
03
天不生陈志龙,职场万古如长夜
04-06
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式