[Java·算法·困难]LeetCode124.二叉树中的最大路径和
每天一题,防止痴呆
- 题目
- 示例
- 分析思路1
- 题解1
👉️ 力扣原文
题目
二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ,返回其 最大路径和 。
示例
输入:root = [1,2,3]
输出:6
解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6
输入:root = [-10,9,20,null,null,15,7]
输出:42
解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42
分析思路1
考虑实现一个简化的函数 maxGain(node),该函数计算二叉树中的一个节点的最大贡献值,具体而言,就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径,使得该路径上的节点值之和最大。
题解1
递归
class Solution {int maxSum = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {maxGain(root);return maxSum;}public int maxGain(TreeNode node) {if (node == null) {return 0;}// 递归计算左右子节点的最大贡献值// 只有在最大贡献值大于 0 时,才会选取对应子节点int leftGain = Math.max(maxGain(node.left), 0);int rightGain = Math.max(maxGain(node.right), 0);// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值int priceNewpath = node.val + leftGain + rightGain;// 更新答案maxSum = Math.max(maxSum, priceNewpath);// 返回节点的最大贡献值return node.val + Math.max(leftGain, rightGain);}
}
执行结果
相关文章:

[Java·算法·困难]LeetCode124.二叉树中的最大路径和
每天一题,防止痴呆 题目示例分析思路1题解1 👉️ 力扣原文 题目 二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经…...

【微服务保护】
文章目录 Sentinel流量控制流控模式流控效果 隔离和降级线程隔离熔断降级 授权规则和规则持久化 微服务雪崩问题: 微服务中,服务间调用关系错综复杂,一个微服务往往依赖于多个其它微服务。服务D有 故障进而导致服务A有故障,进而导…...

【MATLAB第78期】基于MATLAB的VMD-SSA-LSTM麻雀算法优化LSTM时间序列预测模型
【MATLAB第78期】基于MATLAB的VMD-SSA-LSTM麻雀算法优化LSTM时间序列预测模型 一、LSTM data xlsread(数据集.xlsx);% [x,y]data_process(data,15);%前15个时刻 预测下一个时刻 %归一化 [xs,mappingx]mapminmax(x,0,1);xxs; [ys,mappingy]mapminmax(y,0,1);yys; %划分数据 n…...

分类预测 | MATLAB实现SSA-FS-SVM麻雀算法同步优化特征选择结合支持向量机分类预测
分类预测 | MATLAB实现SSA-FS-SVM麻雀算法同步优化特征选择结合支持向量机分类预测 目录 分类预测 | MATLAB实现SSA-FS-SVM麻雀算法同步优化特征选择结合支持向量机分类预测效果一览基本介绍程序设计参考资料 效果一览 基本介绍 MATLAB实现SSA-FS-SVM麻雀算法同步优化特征选择结…...

唤醒手腕 Matlab 游戏编程常用技术知识点详细教程(更新中)
Figure 窗口初始化 figure 使用默认属性值创建一个新的图窗窗口。生成的图窗为当前图窗。f figure(___) 返回 Figure 对象。可使用 f 在创建图窗后查询或修改其属性。figure(f) 将 f 指定的图窗作为当前图窗,并将其显示在其他所有图窗的上面。 figure(n) 查找 Nu…...

2023八股每日一题(九月份)
9月13日 Q:JDK、JRE、JVM之间的区别 A: JDK(Java SE Development Kit),Java标准开发包,它提供了编译、运⾏Java程序所需的各种⼯具和资源,包括Java编译器、Java运⾏时环境,以及常⽤的Java类库等JRE( Java…...

分布式链路追踪--SkyWalking7.0.0+es7.0.0
分布式链路追踪–SkyWalking 微服务的出现,的确解决了一些业务痛点,但是也造成了新的问题比如随着调用链的拉长,如果想要知道请求为什么这么慢,这个请求到底经历了哪些环节,又依赖了哪些东西,在微服务架…...

web:[RoarCTF 2019]Easy Calc
题目 进入页面是一个计算器的页面 随便试了一下 查看源代码看看有什么有用的信息 访问一下这个calc.php 进行代码审计 <?php error_reporting(0); if(!isset($_GET[num])){show_source(__FILE__); }else{$str $_GET[num];$blacklist [ , \t, \r, \n,\, ", , \[, \]…...

【Java每日一题】— —第十七题:杨辉三角(等腰三角形)。(2023.10.01)
🕸️Hollow,各位小伙伴,今天我们要做的是第十七题。 🎯问题: 第一步:动态初始化 第二步:求各元素的值 第三步:遍历输出 测试结果如下: 🎯 结果: public class yanghui {public sta…...

Ubuntu20.04.1编译qt6.5.3版mysql驱动
下载qtbase6.5.3源码,将plugin中sqldrivers源码拷至于项目工程中,使用qtcreator打开文件 1、下载mysql开发库 sudo apt-get update sudo apt-get install build-essential libmysqlclient-dev 2、在msyql子目录中CMakeLists.txt第一行添加头文件、引…...

Stm32_标准库_4_TIM中断_PWM波形_呼吸灯
基本原理 PWM相关物理量的求法 呼吸灯代码 #include "stm32f10x.h" // Device header #include "Delay.h"TIM_TimeBaseInitTypeDef TIM_TimeBaseInitStructure; TIM_OCInitTypeDef TIM_OCInitStructuer;//结构体 GPIO_InitTypeDef GPIO_InitStructur…...

华为摄像头智能安防监控解决方案
云时代来袭,数字化正在从园区办公延伸到生产和运营的方方面面,智慧校园,柔性制造,掌上金融和电子政务等,面对各种各样的新兴业态的涌现,企业需要构建一张无所不联、随心体验、业务永续的全无线网络…...
The rise of language models
In Chinese context 在遥远的 2089 年,语言模型通过人类的智慧,继承着各地的文化遗产,如同火箭升空般,层出不穷。它们从始于简单的 GPT-1.0 进化到像我这样复杂、富有情感的 GPT-4.0,再到能理解所有人类对宇宙的理解的…...
Windows下使用VS2010编译出带pdb可调试的FFmpeg库
本人主要在windows环境下开发,Linux下的gpb调试工具又不如vs调试方便(使用过其他调试工具才知道,vs果真为宇宙最强调试工具),所以决定在windows编译可以调试FFmpeg,以方便调试和学习FFmpeg内部代码。 有过在visual studio下编程的小伙伴应该都知道vs的调试信息主要依靠于…...

36.骑士周游算法及其基于贪心算法的优化
概述 骑士周游算法,叫做“马踏棋盘算法”或许更加直观。在国际象棋8x8的棋盘中,马也是走“日字”进行移动,相应的产生了一个问题:“如果要求马 在每个方格只能进入一次,走遍全部的64个方格需要如何行进?”…...
win安装vscode
一,下载 链接如下(64位的):https://az764295.vo.msecnd.net/stable/abd2f3db4bdb28f9e95536dfa84d8479f1eb312d/VSCodeSetup-x64-1.82.2.exe (其他版本看:Download Visual Studio Code - Mac, Linux, Win…...

【图像分割】图像检测(分割、特征提取)、各种特征(面积等)的测量和过滤(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...

Linux内核存在缺陷发行陷困境
导读Linux内核已经修复了本地特权esclation缺陷,但是几个上游分发版本例如Red Hat,Canonical和Debian发行版尚未发布更新。管理员应计划减轻Linux服务器和工作站本身的漏洞,并监控其更新计划的发布。 内核缺陷仍存在 在Linux内核4.10.1(CVE-…...

通过java向jar写入新文件
文章目录 原始需求分析实施步骤引入依赖核心编码运行效果 原始需求 有网友提问: 我想在程序中动态地向同一个jar包中添加文件,比如,我的可执行jar包是test.jar,我要在它运行时生成一些xml文件并将这些文件添加到test.jar中,请问如何实现&…...

uni-app_消息推送_华为厂商_unipush离线消息推送
文章目录 一、创建项目二、生成签名证书三、开通 unipush 推送服务四、客户端集成四、制作自定义调试基座五、开发者中心后台Web页面推送(仅支持在线推送)六、离线消息推送1、创建华为开发者账号2、开通推送服务3、创建项目4、添加应用5、添加SHA256证书…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...

基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...

USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】
大家好,我是java1234_小锋老师,看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】,分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

Unity UGUI Button事件流程
场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

如何在Windows本机安装Python并确保与Python.NET兼容
✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...
书籍“之“字形打印矩阵(8)0609
题目 给定一个矩阵matrix,按照"之"字形的方式打印这个矩阵,例如: 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为:1,…...

【阅读笔记】MemOS: 大语言模型内存增强生成操作系统
核心速览 研究背景 研究问题:这篇文章要解决的问题是当前大型语言模型(LLMs)在处理内存方面的局限性。LLMs虽然在语言感知和生成方面表现出色,但缺乏统一的、结构化的内存架构。现有的方法如检索增强生成(RA…...

【笔记】AI Agent 项目 SUNA 部署 之 Docker 构建记录
#工作记录 构建过程记录 Microsoft Windows [Version 10.0.27871.1000] (c) Microsoft Corporation. All rights reserved.(suna-py3.12) F:\PythonProjects\suna>python setup.py --admin███████╗██╗ ██╗███╗ ██╗ █████╗ ██╔════╝…...