【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 函…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
