当前位置: 首页 > news >正文

[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)

&#x1f578;️Hollow&#xff0c;各位小伙伴&#xff0c;今天我们要做的是第十七题。 &#x1f3af;问题&#xff1a; 第一步:动态初始化 第二步:求各元素的值 第三步:遍历输出 测试结果如下&#xff1a; &#x1f3af; 结果&#xff1a; public class yanghui {public sta…...

Ubuntu20.04.1编译qt6.5.3版mysql驱动

下载qtbase6.5.3源码&#xff0c;将plugin中sqldrivers源码拷至于项目工程中&#xff0c;使用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…...

华为摄像头智能安防监控解决方案

云时代来袭&#xff0c;数字化正在从园区办公延伸到生产和运营的方方面面&#xff0c;智慧校园&#xff0c;柔性制造&#xff0c;掌上金融和电子政务等&#xff0c;面对各种各样的新兴业态的涌现&#xff0c;企业需要构建一张无所不联、随心体验、业务永续的全无线网络&#xf…...

The rise of language models

In Chinese context 在遥远的 2089 年&#xff0c;语言模型通过人类的智慧&#xff0c;继承着各地的文化遗产&#xff0c;如同火箭升空般&#xff0c;层出不穷。它们从始于简单的 GPT-1.0 进化到像我这样复杂、富有情感的 GPT-4.0&#xff0c;再到能理解所有人类对宇宙的理解的…...

Windows下使用VS2010编译出带pdb可调试的FFmpeg库

本人主要在windows环境下开发,Linux下的gpb调试工具又不如vs调试方便(使用过其他调试工具才知道,vs果真为宇宙最强调试工具),所以决定在windows编译可以调试FFmpeg,以方便调试和学习FFmpeg内部代码。 有过在visual studio下编程的小伙伴应该都知道vs的调试信息主要依靠于…...

36.骑士周游算法及其基于贪心算法的优化

概述 骑士周游算法&#xff0c;叫做“马踏棋盘算法”或许更加直观。在国际象棋8x8的棋盘中&#xff0c;马也是走“日字”进行移动&#xff0c;相应的产生了一个问题&#xff1a;“如果要求马 在每个方格只能进入一次&#xff0c;走遍全部的64个方格需要如何行进&#xff1f;”…...

win安装vscode

一&#xff0c;下载 链接如下&#xff08;64位的&#xff09;&#xff1a;https://az764295.vo.msecnd.net/stable/abd2f3db4bdb28f9e95536dfa84d8479f1eb312d/VSCodeSetup-x64-1.82.2.exe &#xff08;其他版本看&#xff1a;Download Visual Studio Code - Mac, Linux, Win…...

【图像分割】图像检测(分割、特征提取)、各种特征(面积等)的测量和过滤(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

Linux内核存在缺陷发行陷困境

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

通过java向jar写入新文件

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

uni-app_消息推送_华为厂商_unipush离线消息推送

文章目录 一、创建项目二、生成签名证书三、开通 unipush 推送服务四、客户端集成四、制作自定义调试基座五、开发者中心后台Web页面推送&#xff08;仅支持在线推送&#xff09;六、离线消息推送1、创建华为开发者账号2、开通推送服务3、创建项目4、添加应用5、添加SHA256证书…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...