力扣0124——二叉树的最大路径和
二叉树的最大路径和
难度:困难
题目描述
二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ,返回其 最大路径和 。
示例1
输入: root = [1,2,3]
输出: 6
示例2
输入: root = [-10,9,20,null,null,15,7]
输出: 42
题解
因为每个节点只能遍历一次,所以当选择的根节点不为最顶层的节点的时候,叶子节点只能选择一个,可以利用回溯算法,将两个叶子节点其中的最大值(需要大于0)和当前节点的和与0进行比较的结果返回,回溯结束之后就可以得到最终结果
想法代码
public class TreeNode
{public int val;public TreeNode left;public TreeNode right;public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null){this.val = val;this.left = left;this.right = right;}
}public class Solution
{public static void Main(string[] args){Solution solution = new Solution();TreeNode root = new TreeNode{val = -10,left = new TreeNode(9),right = new TreeNode{val = 20,left = new TreeNode(15),right = new TreeNode(7)}};int x = solution.MaxPathSum(root);Console.WriteLine(x);}public int ans = int.MinValue;public int MaxPathSum(TreeNode root){BackTrack(root);return ans;}public int BackTrack(TreeNode root){if (root == null){return 0;}int left = BackTrack(root.left);int right = BackTrack(root.right);int current = Math.Max(0, left) + Math.Max(0, right) + root.val;ans = Math.Max(current, ans);return Math.Max(0, Math.Max(left, right)) + root.val;}
}
相关文章:
力扣0124——二叉树的最大路径和
二叉树的最大路径和 难度:困难 题目描述 二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。 路径和 是路径中各节点…...
c# 字符串帮助类
public class StringHelper { #region 全角半角互相转换 /// <summary> /// 转全角的函数(SBC case) /// </summary> /// <param name"str">任意字符串</param> /// <returns>全…...
LabVIEW双光子荧光显微成像系统开发
双光子显微成像是一种高级荧光显微技术,广泛用于生物学和医学研究,尤其是用于活体组织的深层成像。在双光子成像过程中,振镜(Galvo镜)扮演了非常关键的角色,它负责精确控制激光束在样本上的扫描路径。以下是…...
Prim模板
通过代码探索Prim算法:最小生成树之旅 在计算机科学领域,图算法占据了至关重要的位置,尤其是在设计高效的网络(无论是社交网络、计算机网络还是交通网)时。在这些算法中,寻找最小生成树(MST&am…...
CSS之盒子模型
盒子模型 01-选择器 结构伪类选择器 基本使用 作用:根据元素的结构关系查找元素。 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IE…...
Linux系统安装(CentOS Vmware)
学习环境安装 VMware安装 VMware下载&安装 访问官网:https://www.vmware.com 在此处可以选择语言 点击China(简体中文) 点击产品,点击Workstation Pro 下滑,点击下载试用版 下滑找到Workstation 17 Pro for Wi…...
STM32 硬件随机数发生器(RNG)
STM32 硬件随机数发生器 文章目录 STM32 硬件随机数发生器前言第1章 随机数发生器简介1.1 RNG主要特性1.2.RNG应用 第2章 RNG原理框图第3章 RNG相关寄存器3.1 RNG 控制寄存器 (RNG_CR)3.2 RNG 状态寄存器 (RNG_SR)3.3 RNG 数据寄存器 (RNG_DR) 第3章 RNG代码部分第4章 STM32F1 …...
Window环境下使用go编译grpc最新教程
网上的grpc教程都或多或少有些老或者有些问题,导致最后执行生成文件时会报很多错。这里给出个人实践出可执行的编译命令与碰到的报错与解决方法。(ps:本文代码按照煎鱼的教程编写:4.2 gRPC Client and Server - 跟煎鱼学 Go (gitbook.io)&…...
STM32——FLASH(1)简单介绍、分类、读写流程及注意事项
文章目录 FLASH的特点Nor flash和nand flashflash的读写flash 的存储单位 flash的读写过程 FLASH的特点 可擦写数据可修改可重写访问速度<ROM Nor flash和nand flash Nor flash 1、与SDRAM相似,用户可以直接运行装载到NORFLASH里面的代码,减少SRAM…...
MySQL的DML语言
DML:Data Manipulation Language(数据操作语言) DML语言用来对数据库中表的数据记录进行增、删、改操作。 一、添加数据命令 注意: 插入数据时,指定的字段顺序需要与值的顺序是一一对应的。 字符串和日期型数据应该包…...
Vivado-IP核
Vivado-IP核 主程序 timescale 1ns / 1ps ////module ip_clk_wiz(input sys_clk,input sys_rst_n,output clk_out1,output clk_out2,output clk_out3,output clk_out4,output locked);clk_wiz_0 instance_name(// Clock out ports.clk_out1(clk_out1), // output clk_out…...
品牌如何营造生活感氛围?媒介盒子分享
「生活感」简而言之是指人们对生活的感受和意义,它往往没有充斥在各种重要的场合和事件中,而是更隐藏在细碎平凡的生活场景中。在营销越来越同质化的当下,品牌应该如何打破常规模式,洞察消费情绪,找到更能打动消费者心…...
Java 学习和实践笔记(2)
今天的学习进度: 注册并下载安装好了Java 8,之后进行以下配置。 1)path 是一个常见的环境变量,它告诉系统除了在当前的目标下妹寻找此程序外,还可以到path指定的目录下找。这句话是什么意思呢?以下举报例…...
Python:批量url链接保存为PDF
我的数据是先把url链接获取到存入excel中,后续对excel做的处理,各位也可以直接在程序中做处理,下面就是针对excel中的链接做批量处理 excel内容格式如下(涉及具体数据做了隐藏) 标题文件链接文件日期网页标题1http://…...
【LeetCode每日一题】525连续数组 303区域和检索(前缀和的基本概念和3个简单案例)
前缀和 // 构造prefix let prefix [0] arr.forEach(num > {prefix.push(prefix.at(-1) num); })如果想要计算某个区间 i 到 j 这个子数组的和时,可以根据 prefix[j1] - prefix[i] 获得。 例题1:303.区域和检索 - 数组不可变 给定一个整数数组 num…...
形态学算法应用之连通分量提取的python实现——图像处理
原理 连通分量提取是图像处理和计算机视觉中的一项基本任务,旨在识别图像中所有连通区域,并将它们作为独立对象处理。在二值图像中,连通分量通常指的是所有连接在一起的前景像素集合。这里的“连接”可以根据四连通或八连通的邻接关系来定义…...
Kafka系列之:Kafka集群同时设置基于时间和日志大小两种方式保存Topic的数据
Kafka系列之:Kafka集群同时设置基于时间和日志大小两种方式保存Topic的数据 一、基于日志大小二、基于时间大小三、参数设置四、设置命令一、基于日志大小 "log.retention.bytes"是Apache Kafka中的一项配置参数,用于指定每个日志段文件的最大大小。当日志段文件的…...
pytest+allure批量执行测试用例
在 Pytest 中,可以使用装饰器 `@pytest.fixture` 来定义用例级别的前置和后置操作。下面是一个示例代码,演示了如何使用 Pytest 的前置和后置操作: ```python import pytest @pytest.fixture(scope="function") def setup_function(): print("Setup fu…...
SpringBoot和SpringMVC
目录 一、springboot项目 (1)创建springboot项目 (2)目录介绍 (3)项目启动 (4)运行一个程序 (5)通过其他方式创建和运行springboot项目 二、SpringMVC…...
免费搭建幻兽帕鲁服务器,白嫖阿里云游戏服务器
阿里云幻兽帕鲁服务器免费搭建方案,先在阿里云高校计划「云工开物」活动领取学生专享300元无门槛代金券,幻兽帕鲁专用服务器4核16G配置26元1个月、149元半年,直接使用这个无门槛300元代金券抵扣即可免费搭建幻兽帕鲁服务器。阿里云服务器网al…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
Vue ③-生命周期 || 脚手架
生命周期 思考:什么时候可以发送初始化渲染请求?(越早越好) 什么时候可以开始操作dom?(至少dom得渲染出来) Vue生命周期: 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...
基于江科大stm32屏幕驱动,实现OLED多级菜单(动画效果),结构体链表实现(独创源码)
引言 在嵌入式系统中,用户界面的设计往往直接影响到用户体验。本文将以STM32微控制器和OLED显示屏为例,介绍如何实现一个多级菜单系统。该系统支持用户通过按键导航菜单,执行相应操作,并提供平滑的滚动动画效果。 本文设计了一个…...
