力扣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…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
