1373. 二叉搜索子树的最大键值和
Problem: 1373. 二叉搜索子树的最大键值和
文章目录
- 思路
- 解题方法
- 复杂度
- Code
思路
解决这个问题的关键在于采用深度优先搜索(DFS)策略,并结合树形动态规划的思想。我们需要设计一个递归函数,它不仅能够遍历整棵树,还能收集到每个子树是否为BST的信息、该子树的最大值、最小值、总和以及最重要的是,以该节点为根的BST所能得到的最大键值和。
解题方法
我提出的解题方法是通过定义一个辅助类Info,用来存储递归过程中需要传递的五个关键信息:当前子树的最大值、最小值、作为BST时的最大键值和、子树的总和以及该子树是否为BST的布尔标记。递归函数f(TreeNode x)负责计算以x为根的子树的各种信息,并返回一个Info对象。
复杂度
时间复杂度:
O ( n ) O(n) O(n),每个节点被访问一次,其中n是树中的节点数。
空间复杂度:
O ( n ) O(n) O(n),递归调用栈的深度在最坏情况下会达到树的高度,即n(对于极端不平衡的树),但平均情况下要小得多。
Code
/*** 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 {public class Info{public int max;public int min;public int maxBstSum;public int sum;public boolean isBst;public Info(int max, int min, int maxBstSum, int sum, boolean isBst) {this.max = max;this.min = min;this.maxBstSum = maxBstSum;this.sum = sum;this.isBst = isBst;}}public int maxSumBST(TreeNode root) {return f(root).maxBstSum;}public Info f(TreeNode x) {if(x == null) {return new Info(Integer.MIN_VALUE, Integer.MAX_VALUE, 0, 0, true);}Info infol = f(x.left);Info infor = f(x.right);int max = Math.max(x.val, Math.max(infol.max, infor.max));int min = Math.min(x.val, Math.min(infol.min, infor.min));int sum = infol.sum + infor.sum +x.val;boolean isBst = infol.isBst && infor.isBst && infol.max < x.val && x.val < infor.min;int maxBstSum = Math.max(infol.maxBstSum, infor.maxBstSum);if(isBst) {maxBstSum = Math.max(maxBstSum, sum);}return new Info(max, min, maxBstSum, sum, isBst);}
}
相关文章:
1373. 二叉搜索子树的最大键值和
Problem: 1373. 二叉搜索子树的最大键值和 文章目录 思路解题方法复杂度Code 思路 解决这个问题的关键在于采用深度优先搜索(DFS)策略,并结合树形动态规划的思想。我们需要设计一个递归函数,它不仅能够遍历整棵树,还能…...
基于java + Springboot 的二手物品交易平台实现
目录 📚 前言 📑摘要 📑系统架构 📚 数据库设计 📚 系统功能的具体实现 💬 登录模块 首页模块 二手商品轮播图添加 💬 后台功能模块 二手商品商品列表 添加二手商品商品 添加购物车 &a…...
Shopee本土店选品有什么技巧?EasyBoss ERP为你整理了6个高效选品的方法!
电商圈有句话叫:七分靠选品,三分靠运营,选品对了,事半功倍,选品错了,功亏一篑! 很多卖家都会为选品发愁,特别对于Shopee本土店卖家来说,要囤货到海外仓,如果…...
3D在线展览馆的独特魅力,技术如何重塑展览业的未来?
在数字化和虚拟现实技术迅猛发展的今天,3D在线展览馆已经成为一种颇具前景的创新形式。搭建3D在线展览馆不仅能够突破传统展览的时空限制,还能为参观者提供身临其境的体验,极大地提升展示效果和用户互动。 一、3D在线展览馆的意义 1、突破时空…...
基于SpringBoot的藏区特产销售平台
你好呀,我是计算机学姐码农小野!如果有相关需求,可以私信联系我。 开发语言: Java 数据库: MySQL 技术: SpringBoot框架 工具: MyEclipse 系统展示 首页 个人中心 特产信息管理 订单管…...
hudi系列-schema evolution(一)
hudi+flink在非schema on read模式下也表现出了支持一部分的schema evolution功能,本篇中测试一下在非schema on read模式下,发生各种列变更情况时数据写入与读取情况。 flink 1.14.5hudi 0.13.1mor表思路: 选择mor表是因为它的数据文件有avro和parquet两种格式,能覆盖得更…...
Redis-实战篇-缓存雪崩
文章目录 1、缓存雪崩2、解决方案: 1、缓存雪崩 缓存雪崩是指在同一时段大量的缓存key同时失效或者Redis服务宕机,导致大量请求到达数据库,带来巨大压力。 2、解决方案: 给不同的key的TTL添加随机值利用Redis集群提高服务的可用性…...
线性代数|机器学习-P18快速下降奇异值
文章目录 1. 为什么要低秩矩阵1.1 矩阵A的秩定义1.2 矩阵压缩PCA 2. 低秩矩阵图像处理3. 秩的相关性质3.1 秩的公差轴表示3.2 Eckart-Young 定理 4. 低秩矩阵4.1 低秩矩阵描述4.2 函数低秩矩阵形式4.3通项小结4.4 函数采样拟合 5. 西尔维斯特方程5.1 希尔伯特矩阵举例5.2 范德蒙…...
本地离线模型搭建指南-中文大语言模型底座选择依据
搭建一个本地中文大语言模型(LLM)涉及多个关键步骤,从选择模型底座,到运行机器和框架,再到具体的架构实现和训练方式。以下是一个详细的指南,帮助你从零开始构建和运行一个中文大语言模型。 本地离线模型搭…...
【代码随想录】【算法训练营】【第51天】 [115]不同的子序列 [583]两个字符串的删除操作 [72]编辑距离
前言 思路及算法思维,指路 代码随想录。 题目来自 LeetCode。 day 51,周四,又是不能坚持的一天~ 题目详情 [115] 不同的子序列 题目描述 115 不同的子序列 解题思路 前提: 思路: 重点: 代码实现 …...
24下半年软考集合!30s打破信息差!
01软考是什么? 软考,全称为计算机技术与软件专业技术资格(水平)考试,也称为计算机资格考试,是由国家人力资源和社会保障部、工业和信息化部领导的国家级考试。它既是国家级资格证书,又是职称资…...
如何在Xcode中设置库路径
在Xcode中设置库路径的过程可以分为以下几个步骤,下面将结合参考文章中的信息,以清晰、分点表示和归纳的方式给出指导: 1. 确定库的类型和来源 动态库(.dylib或.framework)或静态库(.a)&#…...
小程序的基本使用
【 0 】前言 【 0 】 这个就是js代码的存放地方 app.json // pages/banner/banner.js Page({/*** 页面的初始数据*/data: {},/*** 生命周期函数--监听页面加载*/onLoad(options) {},/*** 生命周期函数--监听页面初次渲染完成*/onReady() {},/*** 生命周期函数--监听页面显示…...
[保姆级教程]uniapp设置字体引入字体格式
文章目录 在 UniApp 中设置和引入自定义字体(如 .ttf、.woff、.woff2 等格式)通常涉及几个步骤。 准备字体文件: 首先,你需要有字体文件。这些文件通常以 .ttf、.woff 或 .woff2 格式提供。确保有权使用这些字体,并遵守…...
【Webpack】前端工程化之Webpack与模块化开发
目 录 前言模块化开发Stage1 - 文件划分方式Stage2 - 命名空间方式Stage3 - IIFE(立即调用函数表达式)Stage 4 - IIFE 依赖参数模块化的标准规范 使用Webpack实现模块化打包安装WebpackWebpack基本配置Webpack构建流程Webpack热更新Webpack打包优化 前言…...
【Android】记录在自己的AMD处理器无法使用Android studio 虚拟机处理过程
文章目录 问题:无法在AMD平台打开Android studio 虚拟机,已解决平台:AMD 5700g系统:win10专业版1、在 amd平台上使用安卓虚拟机需要安装硬件加速器2、关闭win10上的系统服务 问题:无法在AMD平台打开Android studio 虚拟…...
LearnOpenGL - Android OpenGL ES 3.0 使用 FBO 进行离屏渲染
系列文章目录 LearnOpenGL 笔记 - 入门 01 OpenGLLearnOpenGL 笔记 - 入门 02 创建窗口LearnOpenGL 笔记 - 入门 03 你好,窗口LearnOpenGL 笔记 - 入门 04 你好,三角形OpenGL - 如何理解 VAO 与 VBO 之间的关系LearnOpenGL - Android OpenGL ES 3.0 绘制…...
人工智能虚拟仿真系统,解决算法难、编程难、应用场景难三大难题
近年来,人工智能技术迅猛发展,广泛渗透至各行业,市场份额持续扩大,预示着智能化转型的广阔前景。该行业本质上属于知识高度密集型,近年来的迅猛发展进一步加剧了对专业人才的迫切需求。 然而,我国目前在人工…...
CTE(公共表表达式)和视图在查询时的性能影响
在SQL查询优化和数据库设计中,CTE(公共表表达式)和视图都是常用的工具。尽管它们在功能和使用场景上有很多相似之处,但在查询性能方面可能存在显著差异。本文将探讨CTE和视图在查询时的性能影响,帮助您在实际项目中做出…...
新能源行业必会基础知识-----电力市场概论笔记-----绪论
新能源行业知识体系-------主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/139946830 目录 1. 电力市场的定义2. 对传统电力系统理论的挑战 1. 电力市场的定义 1. 我国电力市场的进程 我国新一轮电力体制改革的5大亮点&…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...
STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
PostgreSQL——环境搭建
一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在࿰…...
Python 高效图像帧提取与视频编码:实战指南
Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...
Python网页自动化Selenium中文文档
1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API,让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API,你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...
Spring AOP代理对象生成原理
代理对象生成的关键类是【AnnotationAwareAspectJAutoProxyCreator】,这个类继承了【BeanPostProcessor】是一个后置处理器 在bean对象生命周期中初始化时执行【org.springframework.beans.factory.config.BeanPostProcessor#postProcessAfterInitialization】方法时…...
