leetcode124 二叉树中的最大路径和-dp

news/2024/7/14 18:59:08/文章来源:https://blog.csdn.net/midi666/article/details/139134415
题目

二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ,返回其 最大路径和 。

示例

输入:root = [-10,9,20,null,null,15,7]
输出:42
解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42
在这里插入图片描述

解析
func maxPathSum(root *TreeNode) int {ans := math.MinIntvar dfs func(*TreeNode) intdfs = func(node *TreeNode) int {if node == nil {return 0 // 没有节点,和为0}leftMaxVal := dfs(node.Left)                         // 左子树最大链和rightMaxVal := dfs(node.Right)                       // 右子树最大链和ans = max(ans, leftMaxVal+rightMaxVal+node.Val)      // 两条链拼成路径return max(max(leftMaxVal, rightMaxVal)+node.Val, 0) // 当前子树最大链和}dfs(root)return ans
}

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

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

相关文章

C++模板方法模式

文章目录 1. 定义抽象基类(Abstract Class)2. 实现具体子类(Concrete Class)3. 使用模板方法模板方法模式的优点模板方法模式的应用场景注意事项实现示例抽象类(模板)具体实现类客户端代码 总结 模板方法模…

Elasticsearch (ES) (上万字)详细学习总结

一、认识ES 二、ES相关安装和部署(elasticsearch 、kbana、ik) 这部分的内容可以查看我之前写的Docker常用部署这篇文章 三、Mapping映射 3.1 Mapping映射属性 3.2 索引库操作 3.2.1 遵循Restful规范说明 3.2.2 具体使用方式说明 3.2.3增删改查示例 #创建 PUT /heima {&q…

【Java面试】四、MySQL篇(上)

文章目录 1、定位慢查询2、慢查询的原因分析3、索引3.1 数据结构选用:二叉树 & 红黑树3.2 数据结构选用:B树 4、聚簇索引、非聚簇索引、回表查询4.1 聚簇索引、非聚簇索引4.2 回表查询 5、覆盖索引、超大分页优化5.1 覆盖索引5.2 超大分页处理 6、索…

存储+调优:存储-memcached

存储调优:存储-memcached 什么是memcached? 高性能的分布式内存缓存服务器。通过缓存数据库的查询结果,减少数据库访问次数,以提高动态Web应用的速度、提高可扩展性。 在memcached中存什么? 尽快被保存 访问频率高 1.数据保…

【Unity】Unity项目转抖音小游戏(三)资源分包,抖音云CDN

业务需求,开始接触一下抖音小游戏相关的内容,开发过程中记录一下流程。 使用资源分包可以优化游戏启动速度,是抖音小游戏推荐的一种方式,抖音云也提供存放资源的CDN服务 抖音云官方文档:https://developer.open-douyi…

R可视化:另类的箱线图

介绍 方格状态的箱线图 加载R包 knitr::opts_chunk$set(echo TRUE, message FALSE, warning FALSE) library(patternplot) library(png) library(ggplot2) library(gridExtra)rm(list ls()) options(stringsAsFactors F)导入数据 data <- read.csv(system.file(&qu…

雷达基数据绘制成雷达图

x波段雷达基数据绘制成雷达图 1.雷达基数据格式Z_RADR_I_ZR001_20240521020002_O_DOR_YLD2-D_CAP_FMT.bin.bz2 2.基数据读取 python f StandardData(i) # 新版本标准数据radarTime f.scantime # 获取雷达时次date_str radarTime.strftime(%Y-%m-%d %H:%M:%S)date_str d…

C#【进阶】排序进阶

排序进阶 文章目录 插入排序希尔排序归并排序快速排序堆排序 插入排序 #region 知识点一 插入排序的基本原理 // 8 7 1 5 4 2 6 3 9 // 两个区域 // 排序区 // 未排序区 // 用一个索引值做分水岭// 未排序区元素 // 与排序区元素比较 // 插入到合适位置 // 直到未排序区清空 #e…

Docker(三) 容器管理

1 容器管理概述 Docker 的容器管理可以通过 Docker CLI 命令行工具来完成。Docker 提供了丰富的命令&#xff0c;用于管理容器的创建、启动、停止、删除、暂停、恢复等操作。 以下是一些常用的 Docker 容器命令&#xff1a; 1、docker run&#xff1a;用于创建并启动一个容器。…

Qt教程3-Ubuntu(x86_64)上配置arm64(aarch64)交叉编译环境及QT编译arm64架构工程

汇创慧玩 写在前面1. 查看系统架构相关指令2. ARM64交叉编译器环境搭建3. Qt编译arm64环境搭建4. 配置 Qt的本地aarch64交叉编译器5. 工程建立及编译验证 写在前面 苦辣酸甜时光八载&#xff0c;春夏秋冬志此一生 Qt简介&#xff1a; Qt&#xff08;官方发音 [kju:t]&#xff…

Spring Boot集成六大常用中间件,附集成源码,亲测有效

目录 万字论文&#xff0c;从0到1&#xff0c;只需1小时获取途径1、Spring Boot如何集成Spring Data JPA&#xff1f;2、Spring Boot如何集成Spring Security&#xff1f;3、Spring Boot如何集成Redis&#xff1f;4、Spring Boot如何集成RabbitMQ&#xff1f;5、Spring Boot如何…

【C++】C++11(一)

C11是一次里程碑式的更新&#xff0c;我们一起来看一看~ 目录 列表初始化&#xff1a;{ }初始化&#xff1a;std::initializer_list&#xff1a; 声明&#xff1a;auto&#xff1a;decltype&#xff1a; STL的一些变化&#xff1a; 列表初始化&#xff1a; { }初始化&#xf…

云计算期末复习(2)

MapReduce 包含Google MapReduce基本构架、Hadoop MapReduce基本构架 作业&#xff08;问答题&#xff09; &#xff08;1&#xff09;预习论文The Google File System&#xff0c;总结和分析GFS主要特点。 GFS的主要特点包括&#xff1a; 1. 高可靠性和容错性&#xff1a;G…

政府鼓励社会力量建设气膜体育场馆—轻空间

2023年12月1日&#xff0c;国家体育安全总局发布的《关于政协第十四届全国委员会第一次会议第00374号&#xff08;文体宣传类020号&#xff09;提案答复的函》中指出&#xff0c;2016年和2020年国务院发布的文件中均涉及推动气膜场馆建设及完善装配式建筑相关政策。下一步&…

炸裂!AI五分钟模仿爆款IP故事,涨粉速度太绝了!

‍ ‍大家好&#xff0c;我是向阳。 今天我要分享一个利用AI技术模仿爆款账号的小技巧&#xff0c;帮助大家迅速增加粉丝。这个方法简单实用&#xff0c;尤其适用于副业和本地生活领域。接下来&#xff0c;我将为大家详细讲解操作步骤。让我们开始吧。 副业赚钱&#xff1a;模…

2024年03月 Python(四级)真题解析#中国电子学会#全国青少年软件编程等级考试

Python等级考试(1~6级)全部真题・点这里 一、单选题(共25题,共50分) 第1题 运行如下代码,若输入整数3,则最终输出的结果为?( ) def f(x):if x==1:s=1else:s

基于 IP 的 DDOS 攻击实验

介绍 基于IP的分布式拒绝服务&#xff08;Distributed Denial of Service, DDoS&#xff09;攻击是一种利用大量受控设备&#xff08;通常是僵尸网络&#xff09;向目标系统发送大量请求或数据包&#xff0c;以耗尽目标系统的资源&#xff0c;导致其无法正常提供服务的攻击方式…

[集群聊天服务器]----(十)Nginx的tcp负载均衡配置--附带截图

接着上文&#xff0c;我们剖析了服务端和客户端的代码&#xff0c;但是单台服务器的并发量是有限的&#xff0c;面对并发量的要求&#xff0c;我们就需要引入Nginx来实现并发量的要求&#xff0c;将用户请求分发到不同的服务器上分担压力&#xff0c;这就是负载均衡。 选择负…

【国信华源:以专业服务,协助水利厅抵御强暴雨】

5月18日-19日&#xff0c;广西出现入汛以来最强暴雨天气过程&#xff0c;钦州、防城港、北海、南宁等地出现特大暴雨&#xff0c;多地打破降雨量极值。国信华源技术团队积极行动驻守一线&#xff0c;为打好山洪灾害防御的提前战、主动战提供了技术支撑。 5月17日18时&#xff0…

在某云服务器上搭建公网kali linux2.0

前提&#xff1a; 可用的 CVM 实例 挂载一个系统盘之外的盘&#xff0c;安装完成后可卸载&#xff01; 创建实例&#xff0c;安装centos7系统&#xff01; 然后执行fdisk -l看磁盘的情况 在这里我将把镜像写入vdb这块数据盘 非 root 的情况下记得sudo执行以下命令 注意&…