124. 二叉树中的最大路径和【 力扣(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
三、解题思路
- 基本思路:
初看这一题,好像没有思路。但是,仔细分析一下,其实每个节点无非就三种情况,一种是成为路径的根,另一种是非根,最后一种就是不选;如果是路径的根,那就要计算其左子树和右子树的路径和;如果是非根,那就选择左右子树最大的一个成为路径的一部分;如果左右子树+本身都是负的,那就不选了这个节点。
个人建议:当碰到无法无从下手的题目,可以从细节考虑,分析可能发生的情况,然后每种情况要怎么处理。 - 具体思路:
- 如果节点为空,则返回 0 ;
- 计算左右子树最大路径;
- 如果选取该节点为根,则更新最大值;
- 如果不选该节点为根,则返回左右子树最大路径,如果为负,则返回 0 ;
四、参考代码
时间复杂度: O ( n ) \Omicron(n) O(n)【n 为节点数】
空间复杂度: O ( n ) \Omicron(n) O(n)
/*** 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 ans = -1000;int maxPathSum(TreeNode* root) {maxPath(root);return ans;}int maxPath(TreeNode* root) {if (!root)return 0;int l, r;l = maxPath(root->left);r = maxPath(root->right);// 选取该节点为根ans = max(ans, l + r + root->val);// 不选return max(0, max(l, r) + root->val);}
};
相关文章:
124. 二叉树中的最大路径和【 力扣(LeetCode) 】
文章目录 零、原题链接一、题目描述二、测试用例三、解题思路四、参考代码 零、原题链接 124. 二叉树中的最大路径和 一、题目描述 二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径…...
echarts:简单实现默认显示两柱子折线,点击按钮后显示新的柱子
问: 用echarts实现:默认显示两柱子折线,点击“税率”按钮,显示税率柱子,之前的两柱子折线消失 回答: <!DOCTYPE html> <html lang"zh"> <head><meta charset"UTF-8…...
视频里的音频怎么提取出来成单独文件?音频提取照着这些方法做
在数字时代,视频与音频的分离与重组已成为日常需求之一。无论是出于制作背景音乐、保存讲座内容,还是编辑播客素材,提取视频中的音频并将其保存为单独文件都显得尤为重要。视频里的音频怎么提取出来成单独文件?本文将详细介绍几种…...
Excel——宏教程(精简版)
一、宏的简介 1、什么是宏? Excel宏是一种自动化工具,它允许用户录制一系列操作并将其转换为VBA(Visual Basic for Applications)代码。这样,用户可以在需要时执行这些操作,以自动化Excel任务。 2、宏的优点 我们可以利用宏来…...
C++中的std::tuple和std::pair
在C标准库中,std::tuple和std::pair是两种极具实用性的数据结构,它们都具备存储多个元素的功能,但各自有其独特的适用环境和特性。本文旨在深入探讨这两者之间的区别,并阐述在不同应用场景下应如何合理选择使用。 一、基本概念 s…...
引力搜索算法
引力搜索算法过程,包括了初始化、适应度评估、质量计算、加速度计算、更新速度和位置的一些步骤。 import numpy as np import random as rd from math import exp, sqrt import matplotlib.pyplot as plt from mpl_toolkits.mplot3d import Axes3D from matplotli…...
【时间之外】IT人求职和创业应知【35】-RTE三进宫
目录 新闻一:京东工业发布11.11战报,多项倍增数据体现工业经济信心提升 新闻二:阿里云100万核算力支撑天猫双11,弹性计算规模刷新纪录 新闻三:声网CEO赵斌:RTE将成为生成式AI时代AI Infra的关键部分 认知…...
Linux的目录结构
/ ├── bin # Binary - 存放用户可以直接使用的基本二进制可执行文件 ├── sbin # System Binaries - 存放系统管理员专用的二进制可执行文件 ├── usr # Unix System Resources - 存放用户使用的软件和库文件 │ ├── bin # Binary - 用户级应用程序…...
python: generator IDAL and DAL using sql server 2019
其它数据库也是一样的思维方式 create IDAL # encoding: utf-8 # 版权所有 2024 ©涂聚文有限公司 # 许可信息查看:言語成了邀功盡責的功臣,還需要行爲每日來值班嗎 # 描述: # Author : geovindu,Geovin Du 涂聚文. # IDE : P…...
命令执行简单
前言:小迪安全2022第一节反弹shell,小迪用的是两台都是云服务器,没有服务器可以在自己的主机上搭建也是可以的,主机上搭两个网站 思路:生成一个木马文件,下载到本机,然后利用本机上传到目标主机…...
【一句话经验】亚马逊云EC2 ubuntu24.04.1开启ROOT登录Permission denied (publickey)
按照常规的方法SSH登录会一直报错: Permission denied (publickey) 因为亚马逊云的默认配置不是在/etc/ssh/sshd_config,而是在引入的文件里了,所以在instance控制台输入这行命令来解除登录限制: sudo sed -i s/^PasswordAuthe…...
百度智能云千帆大模型平台引领企业创新增长
本文整理自百度世界大会 2024——「智能跃迁 产业加速」论坛的同名演讲。 更多大会演讲内容,请访问: https://baiduworld.baidu.com 首先,跟大家分享一张图,这个是我们目前大模型应用落地的场景分布。可以看到,大模型…...
【Linux】深入理解GCC/G++编译流程及库文件管理
目录 1.背景知识 2.gcc/g如何完成编译 (1) 预处理(进行宏替换) (2) 编译(生成汇编) (3) 汇编(生成机器可识别代码) (4) 链接(生成可执行文件或库文件) (5) 总结 (6) 函数库 …...
【Unity基础】对比Unity中两种粒子系统
在Unity中,Particle System和Visual Effect Graph (VFX) 都是用于创建粒子效果的工具,但它们的设计目标、使用场景和功能特点有所不同。以下是详细对比: 1. Particle System 特点 传统粒子系统,Unity自带的模块化粒子特效工具。…...
琐碎笔记——pytest实现前置、后置、参数化、跳过用例执行以及重试
pytest的fixture中文介绍可参考(不过文档稍微有点老): https://www.osgeo.cn/pytest/fixture.html#what-fixtures-are pytest各个作用域的fixture scope “function” 可作用于每个用例 fixture使用的声明放在类定义前面,类中的…...
C# 深层副本与浅层副本 深拷贝与浅拷贝
C# 深层副本与浅层副本 数据复制是编程中的重要任务。 对象是 OOP 中的复合数据类型。 对象中的成员字段可以按值或按引用存储。 可以以两种方式执行复制。 浅表副本将所有值和引用复制到新实例中。 引用所指向的数据不会被复制; 仅指针被复制。 新的引用指向原始…...
CH06_Lambda表达式
第6章:Lambda表达式 本章目标 为什么要学习C#编程语言 了解C#相关常识 C#开发工具Visual Studio安装 掌握C#程序的开发步骤 掌握C#的注释 掌握C#的常用转义符 本章内容 lambda表达式演变史 C# 匿名函数的演变历史可以追溯到 C# 语言的不同版本,…...
大模型本地部署实践:Ollama+Open-WebUI(MacOS)
目录 什么是Ollama Ollama安装 对话界面可视化?Open-WebUI! 安装Open-WebUI 什么是Ollama Ollama是一个为简化大语言模型本地部署与交互的开源框架。它提供了用户友好的接口,帮助开发者和模型爱好者在没有依赖外部API的基础上高效地运行、…...
JavaScript——DOM编程、JS的对象和JSON
一、DOM编程 DOM(Document Object Model)编程:就是使用document对象的API,完成对网页HTML文档进行动态修改,以实现网页数据,和样式动态变化效果的编程。 (一)DOM获取元素的多种方法 1.查找元素的函数 getElementById("id值…...
SIMCom芯讯通A7680C在线升级:FTP升级成功;http升级腾讯云对象储存的文件失败;http升级私有服务器的文件成功
从事嵌入式单片机的工作算是符合我个人兴趣爱好的,当面对一个新的芯片我即想把芯片尽快搞懂完成项目赚钱,也想着能够把自己遇到的坑和注意事项记录下来,即方便自己后面查阅也可以分享给大家,这是一种冲动,但是这个或许并不是原厂希望的,尽管这样有可能会牺牲一些时间也有哪天原…...
Go语言安全编码实践:常见漏洞与防护
Go语言安全编码实践:常见漏洞与防护 1. 安全编码原则 安全编码是防止漏洞的根本,包括输入验证、输出编码、最小权限等原则。 2. 安全工具 package securityimport ("regexp""strings" )type Validator struct {emailRegex *regexp.R…...
下行周期生存之道 = 低风险试错 × 即时反馈 × 长期复购
总结公式: 下行周期赚钱 低风险试错 即时反馈 长期复购 日本用30年验证了这套逻辑。 普通人现在能不能赚到钱,不在于胆子够不够大,而在于你能不能在大家焦虑的时候,给他一点确定感。 先收藏,慢慢找自己的切入口。...
SITS 2026图计算方案深度解析,独家披露金融风控与生物医药两大场景的GNN工程化适配矩阵(含12个可复用配置模板)
更多请点击: https://intelliparadigm.com 第一章:AI原生图计算应用:SITS 2026图神经网络工程化方案 SITS 2026 是面向大规模动态图场景的AI原生图计算框架,深度融合GNN训练、图拓扑实时更新与边缘-云协同推理能力。其核心设计摒…...
如何用DdddOcr在3分钟内构建离线验证码识别系统
如何用DdddOcr在3分钟内构建离线验证码识别系统 【免费下载链接】ddddocr 带带弟弟 通用验证码识别OCR pypi版 项目地址: https://gitcode.com/gh_mirrors/dd/ddddocr 在当今的自动化测试、数据采集和网络安全领域,验证码识别是绕不开的技术难题。传统的在线…...
Unity(十六)切换场景及鼠标相关
场景切换空间命名:using UnityEngine.SceneManagement;直接用代码切换场景有问题要把场景加入到场景列表之中SceneList哪个场景在前面,谁在运行时就会首先进入过时方法Application.LoadLevel()if (Input.GetKeyDown(KeyCode.Space)) {SceneManager.LoadS…...
别再只会addItem了!QT QComboBox的5个高级用法与实战场景(含完整代码)
别再只会addItem了!QT QComboBox的5个高级用法与实战场景(含完整代码) 在QT开发中,QComboBox可能是最容易被低估的控件之一。很多开发者仅仅把它当作一个简单的下拉选择框,用addItem()填充几个静态选项就草草了事。但实…...
Meta发布最大视觉模型:DSG架构如何重构视觉理解范式
1. 项目概述:这不是一次普通更新,而是一次视觉理解边界的重写“Meta Just Updated the Largest Computer Vision Model in History”——这个标题乍看像科技媒体的快讯标题,但如果你在CV领域摸爬滚打过几年,第一反应不是点开链接&…...
基于MCP与Apify的ESG供应链风险智能评估工具实战指南
1. 项目概述:一个为AI工作流赋能的ESG供应链风险智能评估工具 如果你是一名ESG分析师、供应链合规官或者投资经理,那么你一定对“供应商ESG尽职调查”这件事又爱又恨。爱的是,它确实能帮你识别潜在的环境、社会和治理风险,避免“…...
通过 curl 命令在 Ubuntu 终端快速测试 Taotoken 的 API 连通性
🚀 告别海外账号与网络限制!稳定直连全球优质大模型,限时半价接入中。 👉 点击领取海量免费额度 通过 curl 命令在 Ubuntu 终端快速测试 Taotoken 的 API 连通性 在服务器或容器环境中进行开发或部署时,直接使用 curl…...
Active Record Doctor与多数据库支持:MySQL、PostgreSQL、SQLite兼容性详解
Active Record Doctor与多数据库支持:MySQL、PostgreSQL、SQLite兼容性详解 【免费下载链接】active_record_doctor Identify database issues before they hit production. 项目地址: https://gitcode.com/gh_mirrors/ac/active_record_doctor Active Recor…...
