【LeetCode】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.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {private int maxSum = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {maxGain(root);return maxSum;}public int maxGain(TreeNode root) {if(root == null) {return 0;}int left = Math.max(maxGain(root.left), 0);int right = Math.max(maxGain(root.right), 0);maxSum = Math.max(maxSum, root.val + left + right);return root.val + Math.max(left, right);}
}
总结
这道题计算的二叉树的最大路径和对应的路径不一定经过根节点,所以递归函数计算的并不是最大根节点,而是当前节点的“最大贡献值”,也就是以这个节点为头的路径的最大路径和。
相关文章:
【LeetCode】124.二叉树中的最大路径和
题目 二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root &…...
Linux命令总结
1.目录相关命令 绝对路径: 如/etc/init.d当前目录和上层目录: ./ …/主目录: ~/切换目录: c 2.进程相关命令 查看当前进程: ps ps -ef(system v 输出)ps -aux bsd 格式输出ps -ef|grep pid 执…...
SpringBoot临时属性设置
在Spring Boot中,可以通过设置临时属性来覆盖应用程序中定义的属性。这在某些情况下很有用,例如在命令行中指定配置参数或在测试环境中覆盖默认值。 你可以使用--(双破折号)语法来设置临时属性。以下是一些示例: 1. …...
【Python小知识】如何解决代理IP在多线程环境下的并发问题?
前言 在多线程环境下,使用代理IP可能会出现并发问题。具体而言,多个线程可能同时使用同一个代理IP,导致代理IP被封禁或无法访问。为了解决这个问题,我们需要使用一个代理IP池来管理可用的代理IP,并在多线程环境下动态…...
redis常见面试汇总
目录 Redis 适合的场景 Redis 不适合的场景 3、Redis 有哪些常见的功能? 什么是缓存穿透?怎么解决? 什么是缓存雪崩?该如何解决? 参考文献: Redis 适合的场景 缓存:减轻 MySQL 的查询压力…...
子数组的解释与专题
子数组:指在一个数组中,选择一些连续的元素组成的新数组。 例题一:6900. 统计完全子数组的数目 给你一个由 正 整数组成的数组 nums 。 如果数组中的某个子数组满足下述条件,则称之为 完全子数组 : 子数组中 不同 …...
PHP: 开发入门macOS系统下的安装和配置
安装Homebrew 安装 ~~友情提示:这个命令对网络有要求,可能需要翻墙或者用你的手机热点试试,或者把DNS换成(114.114.114.114 和 8.8.8.8) /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebr…...
在CentOS下安装docker
1)在Cent OS安装docker先有一个Cent OS 7.6系统 这个很重要,不同版本按照的时候是不一样的。 2)查看CentOS版本 cat /etc/redhat-releas 3)用root账户登录进去配置国内yum源 wget -O /etc/yum.repos.d/CentOS-Base.repo http:…...
[JavaWeb]SQL介绍-DQL查询数据
SQL介绍-DQL查询数据 一.基础查询二.条件查询三.排序查询1.聚合函数2.分组查询 四.分页查询 DQL查询基础的语法结构如下: SELECT字段列表 FROM表名列表 WHERE条件列表 GROUP BY分组字段 HAVING分组后条件 ORDER BY排序字段 LIMIT分页限定一.基础查询 说明语法查询…...
[containerd] 在Windows上使用IDEA远程调试containerd, ctr, containerd-shim
文章目录 1. containerd安装2. 源码编译3. 验证编译的二进制文件是否含有调试需要的信息3.1. objdump工具验证3.2. file工具验证3.3. dlv工具验证 4. debug 1. containerd安装 [Ubuntu 22.04] 安装containerd 2. 源码编译 主要步骤如下: 1、从github下载containe…...
Verilog语法学习——LV4_移位运算与乘法
LV4_移位运算与乘法 题目来源于牛客网 [牛客网在线编程_Verilog篇_Verilog快速入门 (nowcoder.com)](https://www.nowcoder.com/exam/oj?page1&tabVerilog篇&topicId301) 题目 题目描述: 已知d为一个8位数,请在每个时钟周期分别输出该数乘1/…...
打卡力扣题目九
#左耳听风 ARST 打卡活动重启# 目录 一、问题 二、解题方法一 三、解题方法二 四、两种方法的区别 关于 ARTS 的释义 —— 每周完成一个 ARTS: ● Algorithm: 每周至少做一个 LeetCode 的算法题 ● Review: 阅读并点评至少一篇英文技术文章 ● Tips: 学习至少一个…...
Python零基础入门(九)——函数,类和对象
系列文章目录 个人简介:机电专业在读研究生,CSDN内容合伙人,博主个人首页 Python入门专栏:《Python入门》欢迎阅读,一起进步!🌟🌟🌟 码字不易,如果觉得文章不…...
在linux上面部署activemq
1、下载 网址:ActiveMQ 注意:新版本5.17起 要求jdk11, 5.16兼容jdk8, 所以,确保已经安装 java11 或以上的版本 这里安装较新版:5.18.2,已经安装了java17 如何安装jdk17,请详见我的另一篇文章:linux…...
mysql的sql语句优化方法面试题总结
mysql的sql语句优化方法面试题总结 不要写一些没有意义的查询,如需要生成一个空表结构: select col1,col2 into #t from t where 10 这类代码不会返回任何结果集,但是会消耗系统资源的,应改成这样: create table #t…...
小程序 获取用户头像、昵称、手机号的组件封装(最新版)
在父组件引入该组件 <!-- 授权信息 --><auth-mes showModal"{{showModal}}" idautnMes bind:onConfirm"onConfirm"></auth-mes> 子组件详细代码为: authMes.wxml <!-- components/authMes/authMes.wxml --> <van-popup show…...
【Linux】简易shell外壳的制作
#include <stdio.h> #include <unistd.h> #include <string.h> #include <stdlib.h> #include <sys/types.h> #include <sys/wait.h>#define NUM 1024 #define SIZE 32 #define SEP " "// 保存完整的命令行字符串 char cmd_line…...
TenserRT(四)在 PYTORCH 中支持更多 ONNX 算子
第四章:在 PyTorch 中支持更多 ONNX 算子 — mmdeploy 0.12.0 文档 PyTorch扩充。 PyTorch转换成ONNX: PyTorch有实现。PyTorch可以转化成一个或者多个ONNX算子。ONNX有相应算子。 如果即没有PyTorch实现,且缺少PyTorch与ONNX的映射关系&…...
前端高级面试题-浏览器
1 事件机制 事件触发三阶段 document 往事件触发处传播,遇到注册的捕获事件会触发 传播到事件触发处时触发注册的事件 从事件触发处往 document 传播,遇到注册的冒泡事件会触发 事件触发⼀般来说会按照上⾯的顺序进⾏,但是也有特例&#x…...
Mongodb 多文档聚合操作处理方法三(聚合管道)
聚合 聚合操作处理多个文档并返回计算结果。您可以使用聚合操作来: 将多个文档中的值分组在一起。 对分组数据执行操作以返回单个结果。 分析数据随时间的变化。 要执行聚合操作,您可以使用: 聚合管道 单一目的聚合方法 Map-reduce 函…...
深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
