当前位置: 首页 > news >正文

124. 二叉树中的最大路径和

题目描述

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

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

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

示例 1:

在这里插入图片描述

输入:root = [1,2,3]
输出:6
解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6

示例 2:

在这里插入图片描述

输入:root = [-10,9,20,null,null,15,7]
输出:42
解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42

提示:

  • 树中节点数目范围是 [1, 3 * 104]
  • -1000 <= Node.val <= 1000

解答

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int res = INT_MIN;int maxPathSum(TreeNode* root) {// dfs 求出左子树可得的最大路径和与右子树可得的最大路径和dfs(root);return res;}int dfs(TreeNode *root){if(root == nullptr) return 0;// 自底向上int left = dfs(root->left);int right = dfs(root->right);// 内部的最大路径和,过根节点int in_max = left +root->val + right;res = max(in_max, res);// 子树对外提供的最大路径和,是根到左子树或根到右子树的路径和int out_max = root->val + max(left, right);return max(0, out_max); // 最大路径和为负返回0}
};

相关文章:

124. 二叉树中的最大路径和

题目描述 二叉树中的 路径 被定义为一条节点序列&#xff0c;序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点&#xff0c;且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root &…...

管理类联考——逻辑——论证逻辑——汇总篇——真题和典例——分析

分析 分析争论焦点题 199-2010-1-51——分析争论焦点题——论点争论模型 陈先生&#xff1a;未经许可侵入别人的电脑&#xff0c;就好像开偷来的汽车撞伤了人&#xff0c;这些都是犯罪行为。但后者性质更严重&#xff0c;因为它既侵占了有形财产&#xff0c;又造成了人身伤害…...

深度ip转换器:一键更换ip地址方法

很多网友问小编有关深度ip转换器怎么用&#xff1f;最新深度ip转换器手机版app&#xff1f;下面小编整理了深度ip转换器怎么修改ip地址的技巧和诀窍&#xff0c; 让我们来详细的了解一下深度id转换器&#xff0c; 一、深度ip转换器怎么用 1.深度ip转换器怎么用&#xff0c;深度…...

【TypeScript】类型断言-类型的声明和转换(五)

【TypeScript】类型断言-类型的声明和转换&#xff08;五&#xff09; 【TypeScript】类型断言-类型的声明和转换&#xff08;五&#xff09;一、简介二、断言形式2.1 尖括号语法2.2 as形式 三、断言类型3.1 非空断言3.2 肯定断言-肯定化保证赋值3.3 将任何类型断言为any3.4 调…...

行业追踪,2023-08-10

自动复盘 2023-08-10 凡所有相&#xff0c;皆是虚妄。若见诸相非相&#xff0c;即见如来。 k 线图是最好的老师&#xff0c;每天持续发布板块的rps排名&#xff0c;追踪板块&#xff0c;板块来开仓&#xff0c;板块去清仓&#xff0c;丢弃自以为是的想法&#xff0c;板块去留让…...

Nodejs下动态加载文件夹下的文件模块

个人博客 Nodejs下动态加载文件夹下的文件模块 个人博客&#xff0c;求关注&#xff0c;如果有不够清晰的&#xff0c;麻烦指出来&#xff0c;如果有很不正确的&#xff0c;多谢批评。 文章概叙 本文应用的场景是读取指定文件夹下面的所有文件&#xff0c;然后做操作&#…...

C#实现旋转图片验证码

开发环境&#xff1a;C#&#xff0c;VS2019&#xff0c;.NET Core 3.1&#xff0c;ASP.NET Core 1、建立一个验证码控制器 新建两个方法Create和Check&#xff0c;Create用于创建验证码&#xff08;返回1张图片和令牌&#xff09;&#xff0c;Check用于验证&#xff08;验证图…...

MySQL—缓存

目录标题 为什么要有Buffer Poolbuffer pool有多大buffer pool缓存什么 如何管理Buffer Pool如何管理空闲页如何管理脏页如何提高缓存命中率预读失效buffer pool污染 脏页什么时候会被刷入到磁盘 为什么要有Buffer Pool 虽然说MySQL的数据是存储在磁盘中&#xff0c;但是也不能…...

IP提取器对比器

需求&#xff1a; 一个html 页面 &#xff0c;有两个输入框 第一个输入框输入文本中包含多个ip&#xff0c;输入的ip是不规则的&#xff0c;需要使用正则表达式提取出 输入文本的ip地址 &#xff0c; 然后在第二个输入框中输入内容&#xff0c;并提取出内容的ip &#xff0c;如…...

【Spring Boot】构建RESTful服务 — RESTful简介

RESTful简介 本节将从基础的概念开始介绍什么是RESTful、RESTful的特点、RESTful中的资源、HTTP Method、HTTP Status&#xff0c;还将介绍RESTful和SOAP到底有哪些区别。 1.什么是RESTful RESTful是目前流行的互联网软件服务架构设计风格。REST&#xff08;Representationa…...

模仿火星科技 基于cesium+水平面积测量+可编辑

​ 当您进入Cesium的编辑水平积测量世界&#xff0c;下面是一个详细的操作过程&#xff0c;帮助您顺利使用这些功能&#xff1a; 1. 创建提示窗&#xff1a; 启动Cesium应用&#xff0c;地图场景将打开&#xff0c;欢迎您进入编辑模式。 在屏幕的一角&#xff0c;一个友好的提…...

26.配电网规划——考虑潮流约束的配电网规划

MATLAB代码直达&#xff1a;26.多时段-考虑潮流约束的配电网规划 clc;clear;close all; %% 导入数据 load(data.mat); MGpowerxlsread(MG1-3.xlsx); % 微电网的日负荷曲线 nt3 ; % 变压所个数 Sn25; % 变电所容量 MVA G…...

【云原生】K8S集群

目录 一、调度约束1.1 POT的创建过程1.1调度过程 二、指定节点调度2.1 通过标签选择节点 三、亲和性3.1requiredDuringSchedulingIgnoredDuringExecution&#xff1a;硬策略3.1 preferredDuringSchedulingIgnoredDuringExecution&#xff1a;软策略3.3Pod亲和性与反亲和性3.4使…...

python接口自动化之自动发送测试报告邮件

前言 ​ SMTP&#xff08;Simple Mail Transfer Protocol&#xff09;也就是简单邮件传输协议&#xff0c;是一种提供可靠且有效电子邮件传输的协议。python的smtplib模块就提供了一种很方便的途径发送电子邮件&#xff0c;它对smtp协议进行了简单的封装。 ​ python发邮件主…...

umi出现“Cannot find module ‘umi-build-dev/lib/routes‘“ 错误

确认安装的 Umi 版本是否正确&#xff1a;首先&#xff0c;检查项目中 package.json 文件中的 umi 的版本号是否正确&#xff0c;确保版本号与项目所需的版本一致。清除缓存并重新安装依赖&#xff1a;可以尝试使用以下命令清除 npm 缓存并重新安装依赖&#xff1a; npm cache …...

Redis类型检查与命令多态

Redis中用于操作键的命令基本上可以分为两种类型。 其中一种命令可以对任何类型的键执行&#xff0c;比如说DEL命令、EXPIRE命令 、RENAME命令、TYPE命令、OBJECT命令等。 举个例子&#xff0c;以下代码就展示了使用DEL命令来删除三种不同类型的键: # 字符串键 redis> SE…...

mysql支持的xa具体指的是什么?

在MySQL中&#xff0c;XA指的是一种事务协议&#xff08;eXtended Architecture&#xff09;&#xff0c;用于支持分布式事务。XA协议允许应用程序跨多个独立的数据库资源&#xff08;例如多个MySQL实例&#xff09;执行分布式事务。 具体来说&#xff0c;XA协议提供了以下关键…...

IntelliJ Idea 编译时控制台上中文输出乱码

猜测原因是IDEA启动时未指定编码信息&#xff0c;故与系统编码保持一致&#xff08;windows中文系统默认为GBK编码&#xff09;,当以UTF-8编码进行编译在控制台会以GBK编码输出,从而导致乱码 解决方案 指定Idea启动时JVM的默认编码为UTF-8 Help -> Edit Custom Options P…...

锚框【目标检测】

生成多个锚框 假设输入图像高为h,宽为w,我们以图像每个像素为中心生成不同形状的锚框,缩放比 s∈(0,1],宽高比为r>0。那么锚框的宽度和高度分别为和。当中心位置给定时, 已知宽和高的锚框是确定的。缩放比为锚框高与图像高的比值,然后得到一个正方形锚框面积。 ​​…...

001-Spring boot 启动内置Web容器分析

目录 代码入口上下文容器 加载web容器WebServercreateWebServergetWebServerFactory()&#xff1a;getWebServer(): 执行WebServer#start自动配置读取配置修改配置 代码入口 上下文容器 SpringApplication.run(App.class); //追踪下去发现 context createApplicationContext…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...