【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💖💖💖 又和大家见面了 欢迎来到动画详解数据结构系列 作为一个程序员你不能不掌握的知识 先来自我推荐一波 个人网站欢迎访问以及捐款 推荐阅读 如何低成本搭…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
