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

题目理解与分析:就是在二叉树中找到一条和最大的线。
解题思路:从上往下使用递归,1.迭代计算最大的左孩子长度,迭代计算最大的右孩子长度 2.计算每个节点加上左右孩子的最大长度作为最大值,并每个计算完与最大值比较更新。3. 判断左节点和右节点孰大孰小,更新节点的最大路径。
因为最长的线可能出现在:以叶节点为根的单个路径、以叶节点的父节点为根的回旋路径、以根节点为父节点的回旋路径/单个路径。所以归根到底是记录以每个节点为根的最大路径。
class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right
class Solution:def __init__(self):self.maxSum = float("-inf")def maxPathSum(self, root: TreeNode) -> int:def maxGain(node):if not node:return 0leftGain = max(maxGain(node.left), 0)rightGain = max(maxGain(node.right), 0)priceNewPath = node.val + leftGain + rightGainself.maxSum = max(self.maxSum, priceNewPath)return node.val + max(leftGain, rightGain)maxGain(root)return self.maxSum
相关文章:
【leetcode----二叉树中的最大路径和】
二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root ,…...
Rust: 编译过程中链接器 `cc` 没有找到
这个错误信息表明在编译过程中链接器 cc 没有找到。cc 通常是 C 编译器的符号链接,它指向系统上的实际 C 编译器,如 gcc 或 clang。这个错误通常意味着你的系统缺少必要的编译工具链。 要解决这个问题,你需要确保你的系统上安装了 C 编译器。…...
【vue-3】动态属性绑定v-bind
1、文本动态绑定: <input type"text" v-bind:value"web.url"> 简写: <input type"text" :value"web.url"> 2、文字样式动态绑定 <b :class"{textColor:web.fontStatus}">vue学…...
Rust:多线程环境下使用 Mutex<T> 还是 Arc<Mutex<T>> ?
在 Rust 中,Mutex 本身不是线程不安全的;它提供了内部的线程同步机制。然而,如果你想在多线程环境中共享同一个 Mutex,你需要确保这个 Mutex 可以被多个线程访问。为此,你通常需要使用 Arc<Mutex<T>>。Arc…...
关于如何创建一个可配置的 SpringBoot Web 项目的全局异常处理
前情概要 这个问题其实困扰了我一周时间,一周都在 Google 上旅游,我要如何动态的设置 RestControllerAdvice 里面的 basePackages 以及 baseClasses 的值呢?经过一周的时间寻求无果之后打算决定放弃的我终于找到了一些关键的线索。 当然在此…...
docker三种自定义网络(虚拟网络) overlay实现原理
docker提供了三种自定义网络驱动:bridge、overlay、macvlan。 bridge驱动类似默认的bridge网络模式。 overlay和macvlan是用于创建跨主机网络。 支持自定义网段、网关,docker network create --subnet 172.77.0.0/24 --gateway 172.77.0.1 my_n…...
C#上位机1ms级高精度定时任务
precisiontimer 安装扩展包 添加引用 完整代码 using PrecisionTiming;using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Threading.Tasks; us…...
盘点28个免费域名申请大全
盘点28个免费域名申请大全 免费域名推荐学习使用,免费就意味着没任何保障。 名称稳定时间支持解析模式后缀格式说明地址EU.org28 年NS.eu.org/. 国家简写.eu.org需要审核,稳定性高,限制少,国内访问有问题,可 CFeu.orgp…...
【vue】封装的天气展示卡片,在线获取天气信息
源码 <template><div class"sen_weather_wrapper"><div class"sen_top_box"><div class"sen_left_box"><div class"sen_top"><div class"sen_city">山东</div><qctc-time cl…...
【MySQL】库的操作和表的操作
库的操作和表的操作 一、库的操作1、创建数据库(create)2、字符集和校验规则(1)查看系统默认字符集以及校验规则(2)查看数据库支持的字符集(3)查看数据库支持的字符集校验规则(4)校验…...
【学习笔记】后端(Ⅰ)—— NodeJS(Ⅱ)
NodeJS 3、进阶篇 —— Express框架 3.1、Express 框架介绍 3.2、Express 框架初体验 3.3、使用 3.4、中间件 3.5、托管静态文件 3.6、获取表单数据 3.7、防盗链 3.8、路由模式化 3.8、EJS 模板引擎 3.9、express-generator…...
VMware报平台不支持虚拟化Win10家庭版关闭Hyper-V及内核隔离
1.BIOS中开启虚拟化功能 2.启动或关闭程序中找不到Hyper-v 停止 hypervisorlaunchtype(Windows Hyper-V 启动加载器) 以管理员的身份打开命令行窗口,运行如下命令,关闭停止 Windows Hyper-V 启动加载器 开启 Windows Hyper-V 启…...
简单介绍十款可以免费使用的API测试工具
API开发应该是后端开发最常见的工作,而调试和测试API是非常关键的,这篇文章简单介绍几款常用的工具以供大家参考。 SoapUI SoapUI是很老牌的工具的,在之前Webservice盛行的时候经常会用到。 现在官方推出了Pro版本的ReadyAPI,但要…...
非授权人员进入报警系统
非授权人员进入报警系统基于智能视频分析技术和深度学习技术,非授权人员进入报警系统通过现场已经装好的监控摄像头针对人体进行精准检测,并根据设置的禁入区范围进行判断。通过图像处理和人体识别算法,非授权人员进入报警系统可以在实时监测…...
Mysql基础教程(03):AND
MySQL AND 运算符的用法 本文介绍了 MySQL 中如何在 WHERE 子句中使用 AND 运算符组合多个查询条件过滤查询数据。 当使用 SELECT 查询数据时,如果 WHERE 子句中有多个条件,可以根据需要使用 AND, OR, 或者 NOT 运算符将他们组合起来。本文主要介绍 AN…...
为什么要使用 eval
调用 eval 方法的原因是为了确保模型在进行预测时使用正确的配置。在训练过程中,某些层(如 Dropout 层)的行为是为了正则化而设计的,它们会在每次迭代中随机丢弃一些神经元的输出。而在评估模式下,这些层将不再随机丢弃…...
BCD编码(8421)介绍
概念 BCD (Binary-Coded Decimal) 是一种二进制的数字编码形式,其特点每个十进制数位用4个二进制位来表示。 在网络IO中,你传输一个数字类型最少需要一字节,传输两个数字类型最少需要两字节,但是当你使用BCD编码后传输ÿ…...
前端javascript包管理,npm升级用pnpm
一 pnpm 介绍 pnpm(Package Manager)是一个快速、节省磁盘空间的 JavaScript 包管理器,它是 Node.js 生态系统中 npm 的一个替代品。pnpm 解决了传统包管理工具在处理依赖时的一些痛点,特别是关于存储空间使用和依赖地狱的问题。…...
数据库操作(函数)
函数是一段可以直接被另外一段程序调用的程序或代码 一。字符串函数 1.concat(s1,s1....sn):字符串拼接,将s1,s2,sn拼接为一个字符串 例如: select concat("hello","world"); 2.lower(str&…...
[建堆堆排序的时间复杂度推导]向上建堆向下建堆堆排序的时间复杂度分析推导
💖💖💖欢迎来到我的博客,我是anmory💖💖💖 又和大家见面了 欢迎来到动画详解数据结构系列 作为一个程序员你不能不掌握的知识 先来自我推荐一波 个人网站欢迎访问以及捐款 推荐阅读 如何低成本搭…...
PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
【LeetCode】算法详解#6 ---除自身以外数组的乘积
1.题目介绍 给定一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O…...
Axure 下拉框联动
实现选省、选完省之后选对应省份下的市区...
CppCon 2015 学习:Time Programming Fundamentals
Civil Time 公历时间 特点: 共 6 个字段: Year(年)Month(月)Day(日)Hour(小时)Minute(分钟)Second(秒) 表示…...
