【Leetcode 热题 100】124. 二叉树中的最大路径和

问题背景

二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 r o o t root root,返回其 最大路径和

数据约束

  • 树中节点数目范围是 [ 1 , 3 × 1 0 4 ] [1, 3 \times 10 ^ 4] [1,3×104]
  • − 1000 ≤ N o d e . v a l ≤ 1000 -1000 \le Node.val \le 1000 1000Node.val1000

解题过程

参考 二叉树的直径,这两题除了待求目标,其它是完全一样的。
大体上是将路径拆分成两条自上而下的路线,不断地递归更新最大值即可。

具体实现

/*** 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 {// 注意 static 不是所有情况下都可以加的,要考虑该变量是否需要重置private int res = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {dfs(root);return res;}// 递归方法返回的是当前自上而下的路线上,各个节点之和private int dfs(TreeNode root) {if(root == null) {return 0;}int left = dfs(root.left);int right = dfs(root.right);// 根据左右子树的和来更新答案res = Math.max(res, left + right + root.val);return Math.max(Math.max(left, right) + root.val, 0);}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/493955.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【NLP 16、实践 ③ 找出特定字符在字符串中的位置】

看着父亲苍老的白发和渐渐老态的面容 希望时间再慢一些 —— 24.12.19 一、定义模型 1.初始化模型 ① 初始化父类 super(TorchModel, self).__init__(): 调用父类 nn.Module 的初始化方法,确保模型能够正确初始化。 ② 创建嵌入层 self.embedding n…

jvm栈帧中的动态链接

“-Xss”这一名称并没有一个特定的“为什么”来解释其命名,它更多是JVM(Java虚拟机)配置参数中的一个约定俗成的标识。在JVM中,有多个配置参数用于调整和优化Java应用程序的性能,这些参数通常以一个短横线“-”开头&am…

使用Vscode+EIDE+Jlink开发STM32环境配置教程

环境准备 电脑,最好有梯子。一块开发板。烧录调试工具。比如Jlink。 参考文章 超级馒头神的教程 安装环境 安装Vscode,这里不多说,直接百度下载安装即可。 安装如下插件。 然后重启vscode,就可以看到左侧工具栏有了EIDE图标…

信创技术栈发展现状与展望:机遇与挑战并存

一、引言 在信息技术应用创新(信创)战略稳步推进的大背景下,我国信创技术栈已然在诸多关键层面收获了亮眼成果,不过也无可避免地遭遇了一系列亟待攻克的挑战。信创产业作为我国达成信息技术自主可控这一目标的关键一招&#xff0c…

微信小程序开发入门

实现滚动 需要设置高度和边框 轮播图 差值表达式( {{表达式的值}} ),info数据要写到js文件的data数据中 小程序中常用的事件

cad c# 二次开发 ——动态加载dll 文件制作(loada netloadx)

原理:制作一个dll工具,此dll工具可动态加载调试代码所生成的dll。 using System.Collections.Generic; using System.IO; using System.Reflection; using System.Windows.Forms; using Autodesk.AutoCAD.ApplicationServices.Core; using Autodesk.Aut…

基于AT89C52单片机的6位电子密码锁设计

点击链接获取Keil源码与Project Backups仿真图: https://download.csdn.net/download/qq_64505944/90166684?spm1001.2014.3001.5503 14 部分参考设计如下: 目 录 摘要 1 abstract 2 1 绪论 3 1.1 课题背景 3 1.2 课题的目的和意义 3 1.3 电子密码…

文件解析漏洞中间件(iis和Apache)

IIS解析漏洞 IIS6.X #环境 Windows Server 2003 在iis6.x中&#xff0c;.asp文件夹中的任意文件都会被当做asp文件去执行 在默认网站里创建一个a.asp文件夹并创建一个1.jpg写进我们的asp代码 <%now()%> #asp一句话 <%eval request("h")%> 单独创建一…

ASP.NET|日常开发中数据集合详解

ASP.NET&#xff5c;日常开发中数据集合详解 前言一、数组&#xff08;Array&#xff09;1.1 定义和基本概念1.2 数组的操作 二、列表&#xff08;List<T>&#xff09;2.1 特点和优势2.2 常用操作 三、字典&#xff08;Dictionary<K, V>&#xff09;3.1 概念和用途…

OpenCV putText增加中文支持

OpenCV 默认并不支持中文字符显示&#xff0c;需要增加 freetype 支持&#xff0c;也需正确设置中文字体才能正常显示中文。 OpenCV 2.x 版本没有该模块&#xff0c;而 OpenCV 3.x 及以上版本才正式引入了 freetype 模块 &#xff0c;可检查并更新到较新且包含该模块的版本。 O…

设计模式期末复习

一、设计模式的概念以及分类 二、设计模式的主题和意图 设计模式的主题是关于软件设计中反复出现的问题以及相应的解决方案。这些主题是基于长期实践经验的总结&#xff0c;旨在提供一套可复用的设计思路和框架&#xff0c;以应对软件开发中的复杂性和变化性。 三、面向对象程…

Windows脚本清理C盘缓存

方法一&#xff1a;使用power文件.ps1的文件 脚本功能 清理临时文件夹&#xff1a; 当前用户的临时文件夹&#xff08;%Temp%&#xff09;。系统临时文件夹&#xff08;C:\Windows\Temp&#xff09;。 清理 Windows 更新缓存&#xff1a; 删除 Windows 更新下载缓存&#xff0…

随手记:小程序兼容后台的wangEditor富文本配置链接

场景&#xff1a; 在后台配置wangEditor富文本&#xff0c;可以文字配置链接&#xff0c;图片配置链接&#xff0c;产生的json格式为&#xff1a; 例子&#xff1a; <h1><a href"https://uniapp.dcloud.net.cn/" target"_blank"><span sty…

OpenHarmony-6.IPC/RPC组件

IPC/RPC组件机制 1.基本概念 IPC&#xff1a;设备内的进程间通信&#xff08;Inter-Process Communication&#xff09;。 RPC&#xff1a;设备间的进程间通信&#xff08;Remote Procedure Call&#xff09;。 IPC/RPC用于实现跨进程通信&#xff0c;不同的是前者使用Binder驱…

米思齐图形化编程之ESP32开发指导

在当今充满创意与探索的科技领域&#xff0c;米思齐图形化编程为广大爱好者开启了一扇通往智能硬件控制的便捷之门&#xff0c;尤其是当它与强大的 ESP32相结合时&#xff0c;更是碰撞出无限可能的火花。ESP32作为一款高性能、多功能的微控制器&#xff0c;拥有丰富的外设接口与…

tslib(触摸屏输入设备的轻量级库)的学习、编译及测试记录

目录 tslib的简介tslib的源码和make及make install后得到的文件下载tslib的主要功能tslib的工作原理tslib的核心组成部分tslib的框架和核心函数分析tslib的框架tslib的核心函数ts_setup()的分析(对如何获取设备名和数据处理流程的分析)函数ts_setup()自身的主要代码ts_setup()对…

使用 AI 辅助开发一个开源 IP 信息查询工具:一

本文将分享如何借助当下流行的 AI 工具,一步步完成一个开源项目的开发。 写在前面 在写代码时&#xff0c;总是会遇到一些有趣的机缘巧合。前几天&#xff0c;我在翻看自己之前的开源项目时&#xff0c;又看到了 DDNS 相关的讨论。虽然在 2021 年我写过两篇相对详细的教程&am…

Oracle:数据库的顶尖认证

在信息技术的飞速发展中&#xff0c;Oracle Corporation&#xff08;甲骨文公司&#xff09;以其在数据库领域的卓越成就而闻名遐迩。自1977年成立以来&#xff0c;Oracle已经从一个小型软件公司成长为全球最大的企业级软件公司之一&#xff0c;其产品和技术广泛应用于金融、电…

「配置应用的可见性」功能使用教程

引言 对于「应用可见性」这一概念&#xff0c;可能很多开发者小伙伴还不是很熟悉。简单举一个很典型的场景例子&#xff0c;当你开发的应用需要调起第三方应用时&#xff0c;这里就涉及到应用可见性的问题了&#xff0c;如果不配置相关的应用可见性&#xff0c;则你的应用是无…

flask flask-socketio创建一个网页聊天应用

应用所需环境&#xff1a; python 3.11.11 其他 只需要通过这个命令即可 pip install flask3.1.0 Flask-SocketIO5.4.1 -i https://mirrors.tuna.tsinghua.edu.cn/pypi/web/simple 最好是用conda创建一个新的虚拟环境来验证 完整的pip list如下 Package Version ----…