贪心算法:我要监控二叉树!
监控二叉树题目地址 : https://leetcode-cn.com/problems/binary-tree-cameras/
给定一个二叉树,我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1:
输入:[0,0,null,0,0]
输出:1
解释:如图所示,一台摄像头足以监控所有节点。
示例 2:
输入:[0,0,null,0,null,0,null,null,0]
输出:2
解释:需要至少两个摄像头来监视树的所有节点。上图显示了摄像头放置的有效位置之一。
提示:
- 给定树的节点数的范围是 [1, 1000]。
- 每个节点的值都是 0。
思路
这道题目首先要想,如何放置,才能让摄像头最小的呢?
从题目中示例,其实可以得到启发,我们发现题目示例中的摄像头都没有放在叶子节点上!
这是很重要的一个线索,摄像头可以覆盖上中下三层,如果把摄像头放在叶子节点上,就浪费的一层的覆盖。
所以把摄像头放在叶子节点的父节点位置,才能充分利用摄像头的覆盖面积。
那么有同学可能问了,为什么不从头结点开始看起呢,为啥要从叶子节点看呢?
因为头结点放不放摄像头也就省下一个摄像头, 叶子节点放不放摄像头省下了的摄像头数量是指数阶别的。
所以我们要从下往上看,局部最优:让叶子节点的父节点安摄像头,所用摄像头最少,整体最优:全部摄像头数量所用最少!
局部最优推出全局最优,找不出反例,那么就按照贪心来!
此时,大体思路就是从低到上,先给叶子节点父节点放个摄像头,然后隔两个节点放一个摄像头,直至到二叉树头结点。
此时这道题目还有两个难点:
确定遍历顺序
在二叉树中如何从低向上推导呢?
可以使用后序遍历也就是左右中的顺序,这样就可以在回溯的过程中从下到上进行推导了。
后序遍历代码如下:
注意在以上代码中我们取了左孩子的返回值,右孩子的返回值,即left 和 right, 以后推导中间节点的状态
如何隔两个节点放一个摄像头
此时需要状态转移的公式,大家不要和动态的状态转移公式混到一起,本题状态转移没有择优的过程,就是单纯的状态转移!
来看看这个状态应该如何转移,先来看看每个节点可能有几种状态:
有如下三种:
- 该节点无覆盖
- 本节点有摄像头
- 本节点有覆盖
我们分别有三个数字来表示:
- 0:该节点无覆盖
- 1:本节点有摄像头
- 2:本节点有覆盖
大家应该找不出第四个节点的状态了。
一些同学可能会想有没有第四种状态:本节点无摄像头,其实无摄像头就是 无覆盖 或者 有覆盖的状态,所以一共还是三个状态。
因为在遍历树的过程中,就会遇到空节点,那么问题来了,空节点究竟是哪一种状态呢?空节点表示无覆盖?表示有摄像头?还是有覆盖呢?
回归本质,为了让摄像头数量最少,我们要尽量让叶子节点的父节点安装摄像头,这样才能摄像头的数量最少。
那么空节点不能是无覆盖的状态,这样叶子节点就要放摄像头了,空节点也不能是有摄像头的状态,这样叶子节点的父节点就没有必要放摄像头了,而是可以把摄像头放在叶子节点的爷爷节点上。
所以空节点的状态只能是有覆盖,这样就可以在叶子节点的父节点放摄像头了
接下来就是递推关系。
那么递归的终止条件应该是遇到了空节点,此时应该返回2(有覆盖),原因上面已经解释过了。
代码如下:
递归的函数,以及终止条件已经确定了,再来看单层逻辑处理。
主要有如下四类情况:
- 情况1:左右节点都有覆盖
左孩子有覆盖,右孩子有覆盖,那么此时中间节点应该就是无覆盖的状态了。
如图:
968.监控二叉树2
代码如下:
- 情况2:左右节点至少有一个无覆盖的情况
如果是以下情况,则中间节点(父节点)应该放摄像头:
- left == 0 && right == 0 左右节点无覆盖
- left == 1 && right == 0 左节点有摄像头,右节点无覆盖
- left == 0 && right == 1 左节点有无覆盖,右节点摄像头
- left == 0 && right == 2 左节点无覆盖,右节点覆盖
- left == 2 && right == 0 左节点覆盖,右节点无覆盖
这个不难理解,毕竟有一个孩子没有覆盖,父节点就应该放摄像头。
此时摄像头的数量要加一,并且return 1,代表中间节点放摄像头。
代码如下:
- 情况3:左右节点至少有一个有摄像头
如果是以下情况,其实就是 左右孩子节点有一个有摄像头了,那么其父节点就应该是2(覆盖的状态)
- left == 1 && right == 2 左节点有摄像头,右节点有覆盖
- left == 2 && right == 1 左节点有覆盖,右节点有摄像头
- left == 1 && right == 1 左右节点都有摄像头
代码如下:
从这个代码中,可以看出,如果left == 1, right == 0 怎么办?其实这种条件在情况2中已经判断过了,如图:
968.监控二叉树1
这种情况也是大多数同学容易迷惑的情况。
- 情况4:头结点没有覆盖
以上都处理完了,递归结束之后,可能头结点 还有一个无覆盖的情况,如图:
968.监控二叉树3
所以递归结束之后,还要判断根节点,如果没有覆盖,result++,代码如下:
以上四种情况我们分析完了,代码也差不多了,整体代码如下:
(以下我的代码注释很详细,为了把情况说清楚,特别把每种情况列出来。)
C++代码
在以上代码的基础上,再进行精简,代码如下:
大家可能会惊讶,居然可以这么简短,其实就是在版本一的基础上,使用else把一些情况直接覆盖掉了。
在网上关于这道题解可以搜到很多这种神级别的代码,但都没讲不清楚,如果直接看代码的话,指定越看越晕,所以建议大家对着版本一的代码一步一步来哈,版本二中看不中用!
总结
本题的难点首先是要想到贪心的思路,然后就是遍历和状态推导。
在二叉树上进行状态推导,其实难度就上了一个台阶了,需要对二叉树的操作非常娴熟。
本文转载自微信公众号「代码随想录」,可以通过以下二维码关注。转载本文请联系代码随想录公众号。
推荐系统
微软Win11原版22H2下载_Win11GHOST 免 激活密钥 22H2正式版64位免费下载
语言:中文版系统大小:5.13GB系统类型:Win11微软Win11原版22H2下载_Win11GHOST 免 激活密钥 22H2正式版64位免费下载系统在家用办公上跑分表现都是非常优秀,完美的兼容各种硬件和软件,运行环境安全可靠稳定。Win11 64位 Office办公版(免费)优化 1、保留 Edge浏览器。 2、隐藏“操作中心”托盘图标。 3、保留常用组件(微软商店,计算器,图片查看器等)。 5、关闭天气资讯。
Win11 21H2 官方正式版下载_Win11 21H2最新系统免激活下载
语言:中文版系统大小:4.75GB系统类型:Win11Ghost Win11 21H2是微软在系统方面技术积累雄厚深耕多年,Ghost Win11 21H2系统在家用办公上跑分表现都是非常优秀,完美的兼容各种硬件和软件,运行环境安全可靠稳定。Ghost Win11 21H2是微软最新发布的KB5019961补丁升级而来的最新版的21H2系统,以Windows 11 21H2 22000 1219 专业版为基础进行优化,保持原汁原味,系统流畅稳定,保留常用组件
windows11中文版镜像 微软win11正式版简体中文GHOST ISO镜像64位系统下载
语言:中文版系统大小:5.31GB系统类型:Win11windows11中文版镜像 微软win11正式版简体中文GHOST ISO镜像64位系统下载,微软win11发布快大半年了,其中做了很多次补丁和修复一些BUG,比之前的版本有一些功能上的调整,目前已经升级到最新版本的镜像系统,并且优化了自动激活,永久使用。windows11中文版镜像国内镜像下载地址微软windows11正式版镜像 介绍:1、对函数算法进行了一定程度的简化和优化
微软windows11正式版GHOST ISO镜像 win11下载 国内最新版渠道下载
语言:中文版系统大小:5.31GB系统类型:Win11微软windows11正式版GHOST ISO镜像 win11下载 国内最新版渠道下载,微软2022年正式推出了win11系统,很多人迫不及待的要体验,本站提供了最新版的微软Windows11正式版系统下载,微软windows11正式版镜像 是一款功能超级强大的装机系统,是微软方面全新推出的装机系统,这款系统可以通过pe直接的完成安装,对此系统感兴趣,想要使用的用户们就快来下载
微软windows11系统下载 微软原版 Ghost win11 X64 正式版ISO镜像文件
语言:中文版系统大小:0MB系统类型:Win11微软Ghost win11 正式版镜像文件是一款由微软方面推出的优秀全新装机系统,这款系统的新功能非常多,用户们能够在这里体验到最富有人性化的设计等,且全新的柔软界面,看起来非常的舒服~微软Ghost win11 正式版镜像文件介绍:1、与各种硬件设备兼容。 更好地完成用户安装并有效地使用。2、稳定使用蓝屏,系统不再兼容,更能享受无缝的系统服务。3、为
雨林木风Windows11专业版 Ghost Win11官方正式版 (22H2) 系统下载
语言:中文版系统大小:4.75GB系统类型:雨林木风Windows11专业版 Ghost Win11官方正式版 (22H2) 系统下载在系统方面技术积累雄厚深耕多年,打造了国内重装系统行业的雨林木风品牌,其系统口碑得到许多人认可,积累了广大的用户群体,雨林木风是一款稳定流畅的系统,一直以来都以用户为中心,是由雨林木风团队推出的Windows11国内镜像版,基于国内用户的习惯,做了系统性能的优化,采用了新的系统
雨林木风win7旗舰版系统下载 win7 32位旗舰版 GHOST 免激活镜像ISO
语言:中文版系统大小:5.91GB系统类型:Win7雨林木风win7旗舰版系统下载 win7 32位旗舰版 GHOST 免激活镜像ISO在系统方面技术积累雄厚深耕多年,加固了系统安全策略,雨林木风win7旗舰版系统在家用办公上跑分表现都是非常优秀,完美的兼容各种硬件和软件,运行环境安全可靠稳定。win7 32位旗舰装机版 v2019 05能够帮助用户们进行系统的一键安装、快速装机等,系统中的内容全面,能够为广大用户
番茄花园Ghost Win7 x64 SP1稳定装机版2022年7月(64位) 高速下载
语言:中文版系统大小:3.91GB系统类型:Win7欢迎使用 番茄花园 Ghost Win7 x64 SP1 2022.07 极速装机版 专业装机版具有更安全、更稳定、更人性化等特点。集成最常用的装机软件,集成最全面的硬件驱动,精心挑选的系统维护工具,加上独有人性化的设计。是电脑城、个人、公司快速装机之首选!拥有此系统
相关文章
- 管理微软帐户中的各项隐私项
- Win10网上邻居在哪? Win10桌面显示网上邻居网络图方法
- win10网络一会断一会连怎么解决?
- 导致美国进入紧急状态的勒索事件揭示出的网络安全实践需求
- Win10软件闪退且无网络怎么办?Win10软件闪退且无网络的解决方法
- Clast82:利用谷歌应用商店来传播恶意软件
- 大揭秘:原来黑客是这么破解MCU的
- 惊吓!不打电话骗你了,篡改邮箱诈骗189万欧元,而且还有别的招……
- 针对全球SSH服务器的新型无文件P2P僵尸网络悄然入侵?
- 猎豹极速WiFi纪念版购买系统曝出漏洞
- 遭遇网络攻击损失5.8亿美元理赔却不到一半,企业该如何对待网安险
- 如果深度学习能识别一杯尿,那它也能用来识别恶意软件
- ipad连不上wifi怎么办,5种方法帮你解决
- 腾讯电脑管家中系统急救箱是什么?
- Gartner发布2021年八大安全和风险管理趋势
- 保护DNS服务器的10点方法小结
- 微软成立亚太地区公共部门网络安全执行委员会以策协同应对网络攻击
- BazarLoader恶意软件在使用Slack、BaseCamp云服务进行攻击
热门系统
- 1华硕笔记本&台式机专用系统 GhostWin7 32位正式旗舰版2018年8月(32位)ISO镜像下载
- 2深度技术 Windows 10 x86 企业版 电脑城装机版2018年10月(32位) ISO镜像免费下载
- 3电脑公司 装机专用系统Windows10 x86喜迎国庆 企业版2020年10月(32位) ISO镜像快速下载
- 4雨林木风 Ghost Win7 SP1 装机版 2020年4月(32位) 提供下载
- 5深度技术 Windows 10 x86 企业版 六一节 电脑城装机版 版本1903 2022年6月(32位) ISO镜像免费下载
- 6深度技术 Windows 10 x64 企业版 电脑城装机版2021年1月(64位) 高速下载
- 7新萝卜家园电脑城专用系统 Windows10 x64 企业版2019年10月(64位) ISO镜像免费下载
- 8新萝卜家园 GhostWin7 SP1 最新电脑城极速装机版2018年8月(32位)ISO镜像下载
- 9电脑公司Ghost Win8.1 x32 精选纯净版2022年5月(免激活) ISO镜像高速下载
- 10新萝卜家园Ghost Win8.1 X32 最新纯净版2018年05(自动激活) ISO镜像免费下载
热门文章
常用系统
- 1电脑公司 GhostXpSp3 六一节 电脑城装机版 2022年6月 ISO镜像高速下载
- 2新萝卜家园 Ghost XP SP3系统 电脑城极速纯净版 2022年6月 ISO镜像高速下载
- 3惠普笔记本&台式机专用系统 GhostWin7 32位旗舰版2018年7月(32位)快速版IS下载
- 4深度技术Ghost Win8.1 x32位 特别纯净版2020年11月(免激活) ISO镜像高速下载
- 5雨林木风Ghost Win8.1 (X32) 快速纯净版2019年10月(免激活) ISO镜像快速下载
- 6笔记本系统Ghost Win8.1 (32位) 极速纯净版2019年12月(免激活) ISO镜像高速下载
- 7雨林木风Ghost Win8.1 (X32) 快速纯净版2022年7月(免激活) ISO镜像快速下载
- 8新雨林木风 Windows10 x86 企业装机版2020年11月(32位) ISO镜像高速下载
- 9新萝卜家园 Ghost Win7 x64 SP1 极速版2018年4月(64位) 好用下载
- 10新萝卜家园电脑城专用系统 Windows10 x86 企业版2020年1月(32位) ISO镜像高速下载