【LeetCode】打家劫舍 III [M](递归)
337. 打家劫舍 III - 力扣(LeetCode)
一、题目
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。
除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 。
示例 1:

输入: root = [3,2,3,null,3,null,1] 输出: 7 解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
示例 2:

输入: root = [3,4,5,1,3,null,1] 输出: 9 解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
提示:
- 树的节点数在
[1, 104]范围内 0 <= Node.val <= 104
二、代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public class Info {// 如果要抢劫当前节点的情况下,以当前节点为根节点的整棵树能获得的最大收益是多少public int yes;// 如果不抢劫当前节点的情况下,以当前节点为根节点的整棵树能获得的最大收益是多少public int no;public Info(int y, int n) {yes = y;no = n;}}public int rob(TreeNode root) {// 获取根节点root的Info信息Info ans = process(root);// 两种情况取最大值就是答案return Math.max(ans.no, ans.yes);}public Info process(TreeNode node) {// node节点左子树的信息Info leftInfo = null;// node节点右子树的信息Info rightInfo = null;// 递归手机左右子树的Infoif (node.left != null) {leftInfo = process(node.left);}if (node.right != null) {rightInfo = process(node.right);}// 左子树和右子树不抢根节点情况下整棵树的最大收益int leftNo = 0;int rightNo = 0;// 左子树和右子树抢根节点情况下整棵树的最大收益int leftYes = 0;int rightYes = 0;// 给上面四个变量赋值,如果没有左右子树了,相关的信息就默认为0if (leftInfo != null) {leftNo = leftInfo.no;leftYes = leftInfo.yes;}if (rightInfo != null) {rightNo = rightInfo.no;rightYes = rightInfo.yes;}// 情况一:抢劫node节点的情况下,计算以node节点为根节点的整颗树的最大收益// 这种情况下左右子节点都是不能抢劫的,否则会出发警报。所以这个的答案就是leftNo + rightNo + node.valint yes = leftNo + rightNo + node.val; // 要记得加上node节点本身的价值,因为这种情况还要抢劫node节点// 情况二:不抢劫node节点的情况下,计算以node节点为根节点的整颗树的最大收益// 这种情况下左右子树抢劫也可以,不抢也可以,都不会触发警报,因为没有同时抢劫直接相连的屋子// 所以这个就是取左子树抢劫和不抢劫两种情况的最大收益的最大值 + 右子树抢劫和不抢劫两种情况的最大收益的最大值 这个就是node节点情况二的最大收益int no = Math.max(leftNo, leftYes) + Math.max(rightNo, rightYes);// 返回node节点的Info信息return new Info(yes, no);}
}
三、解题思路
如果两家直接相连的屋子被抢劫,会引发报警。一个节点和另外一点是父子关系就是挨着。
两种情况
- 在x屋子被抢了的情况下,以x为根节点的整棵树获得的最大收益
- 在x屋子不被抢的情况下,以x为根节点的整棵树获得的最大收益
情况一:
如果x屋子要抢的话,那么它的两个左右子节点都不可以抢。
这种情况以x为根的树能做到的最大收益就是左右两个子节点不被抢的最大收益加和 + x节点的val。
情况二:
如果x屋子不抢的话,那么它的两个左右子节点可以抢,也可以不抢。
这种情况以x为根的树能做到的最大收益就是取左孩子的抢和不抢这两种情况的最大收益中的最大值,再取右孩子的抢和不抢这两种情况的最大收益中的最大值,将这两个最大值相加就是x屋子不抢的最大收益值。
相关文章:
【LeetCode】打家劫舍 III [M](递归)
337. 打家劫舍 III - 力扣(LeetCode) 一、题目 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。 除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识…...
设计模式——单例模式
单例模式分为懒汉式和饿汉式两种 在有些系统中,为了节省内存资源、保证数据内容的一致性,对某些类要求只能创建一个实例,这就是所谓的单例模式. 例如,Windows 中只能打开一个任务管理器,这样可以避免因打开多个任务管理…...
json-server环境搭建及使用
json-server环境搭建 一个在前端本地运行,可以存储json数据的server。 基于node环境,可以指定一个 json 文件作为 API 的数据源。 文章目录json-server环境搭建前提下载安装监听服务启动成功修改端口号方式一:方式二:数据操作测试…...
RabbitMQ运行机制
消息的TTL(Time To Live) 消息的TTL就是消息的存活时间。 • RabbitMQ可以对队列和消息分别设置TTL。 • 对队列设置就是队列没有消费者连着的保留时间,也可以对每一个单独的消息做单独的 设置。超过了这个时间,我们认为这个消息…...
【Spring Cloud Alibaba】(三)OpenFeign扩展点实战 + 源码详解
系列目录 【Spring Cloud Alibaba】(一)微服务介绍 及 Nacos注册中心实战 【Spring Cloud Alibaba】(二)微服务调用组件Feign原理实战 本文目录系列目录前言一、Feign扩展点配置二、OpenFeign扩展点配置1. 通过配置文件配置有效范…...
面向对象设计原则
在面向对象的设计过程中, 我们要对代码进行一个设计, 从而提高一个软件系统的可维护性和可复用性, 那么遵从面向对象的设计原则,可以在进行设计方案时减少错误设计的产生,从不同的角度提升一个软件结构的设计水平。 面向对象有以下七大原则:1.单一职责原…...
2022年“网络安全”赛项湖南省赛选拔赛 任务书
2022年“网络安全”赛项湖南省赛选拔赛 任务书2022年“网络安全”赛项湖南省赛选拔赛 任务书A模块基础设施设置/安全加固(200分)B模块安全事件响应/网络安全数据取证/应用安全(400分)C模块 CTF夺旗-攻击 (200分&#x…...
学习笔记:Java 并发编程⑥_并发工具_JUC
若文章内容或图片失效,请留言反馈。 部分素材来自网络,若不小心影响到您的利益,请联系博主删除。 视频链接:https://www.bilibili.com/video/av81461839配套资料:https://pan.baidu.com/s/1lSDty6-hzCWTXFYuqThRPw&am…...
Linux文件隐藏属性(修改与显示):chattr和lsattr
文件除了基本的九个权限以外还有隐藏属性存在,这些隐藏属性对于系统有很大的帮助,尤其是系统安全(Security)上 chattr(配置文件隐藏属性) chattr 【-】【ASacdistu】文件或目录名称 选项与参数:…...
广东省基层就业补贴
基层就业补贴链接:https://www.gdzwfw.gov.cn/portal/v2/guide/11440309MB2D27065K4440511108001 一.申请条件: 1、劳动者到中小微企业、个体工商户、社会组织等就业,或到乡镇(街道)、村居社会管理和公共服务岗位就业…...
高压放大器在超声导波钢轨传播中的应用
实验名称:高压放大器在超声导波钢轨传播中的应用研究方向:无损检测测试目的:超声导波具有传播距离远、检测距离长的特点,在钢轨无损检测领域受到越来越多的关注。本文使用有限元仿真方法和现场实验方法,对钢轨各模态超…...
Java字符串常见拼接方式
目录 最常见的方式 StringBuilder.append()和StringBuffer.append() String类下的cocat()方法 String类下的join()方法 StringUtils.join 项目中使用 不建议在 for 循环中使用 “” 进行字符串拼接 通过字符串连接,可以将两个或多个字符串、字符、整数和浮点…...
商城业务:购物车
人生在世如身处荆棘之中,心不动,人不妄动,不动则不伤;如心动则人妄动,伤其身痛其骨,于是体会到世间诸般痛苦。 1、购物车需求 1)、需求描述: - 用户可以在登录状态下将商品添加到购…...
计算机网络学习笔记(一)
网络是由若干接点和连接这些结点的链路组成。 多个网络通过路由器互联起来构成覆盖范围更大的互联网。 普通用户通过ISP接入因特网。 基于ISP的三层结构因特网 相隔较远的两台主机间通信可能需要经过多个ISP。 有电路交换,报文交换,分组交换三种交换方…...
【单目标优化算法】烟花优化算法(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
微服务项目【秒杀商品展示及商品秒杀】
登录方式调整 第1步:从zmall-common的pom.xml中移除spring-session-data-redis依赖 注意: 1)本次不采用spring-session方式,改用redis直接存储用户登录信息,主要是为了方便之后的jmeter压测; 2)…...
DIDL3_模型选择、复杂度、过欠拟合的相关概念
模型选择、复杂度、过欠拟合的概念模型选择训练误差和泛化误差验证数据集和测试数据集K-则交叉验证(没有足够多数据时使用)过拟合和欠拟合模型容量模型容量的影响估计模型容量控制模型容量数据复杂度处理过拟合的方法(1)ÿ…...
Android 9.0 去除锁屏界面及SystemUI无sim卡拨打紧急电话控件显示功能实现
1.1概述 在9.0的系统rom定制化开发中,关于SystemUI的定制化功能也是比较多的,在SystemUI的锁屏页面和状态栏提示无sim卡拨打紧急电话控件显示等相关提示 的功能中,在有些systemui的定制中是不需要这些功能的,所以需要从systemui中去掉这些功能提示的,这就需要从systemui中…...
AntDB-M设计之内存结构
亚信科技专注通信行业多年,AntDB数据库从诞生开始,就面对通信级的大数据量应用场景挑战,在性能、稳定性、规模化等方面获得了超过10年的通信核心业务系统验证,性能峰值达到每秒百万的通信核心交易量。AntDB-M(AntDB内存…...
互联网舆情监测公司监测哪些内容,TOOM北京舆情监测公司
互联网舆情监测公司是一种提供舆情监测、分析和管理服务的公司,其业务主要涉及互联网舆情监测、数据分析、报告撰写、危机处理等方面。这些公司通过使用各种技术和工具,帮助客户监测他们在互联网上的声誉和品牌形象,并提供相应的建议和解决方…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换
目录 关键点 技术实现1 技术实现2 摘要: 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式(自动驾驶、人工驾驶、远程驾驶、主动安全),并通过实时消息推送更新车…...
