当前位置：首页 > news >正文

数据结构与算法之二叉树: LeetCode 654. 最大二叉树 (Ts版)

news 来源：原创 2025/6/18 21:10:54

最大二叉树

https://leetcode.cn/problems/maximum-binary-tree/

描述

给定一个不重复的整数数组 nums 。最大二叉树可以用下面的算法从 nums 递归地构建:
- 创建一个根节点，其值为 nums 中的最大值
- 递归地在最大值左边的子数组前缀上构建左子树
- 递归地在最大值右边的子数组后缀上构建右子树
- 返回 nums 构建的最大二叉树

示例 1

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]

解释：递归调用如下所示：

[3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
  - 空数组，无子节点。
  - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
    - 空数组，无子节点。
    - 只有一个元素，所以子节点是一个值为 1 的节点。
- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
  - 只有一个元素，所以子节点是一个值为 0 的节点。
  - 空数组，无子节点。

示例 2

输入：nums = [3,2,1]
输出：[3,null,2,null,1]

提示

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums 中的所有整数互不相同

Typescript 版算法实现

1 ) 方案1：递归

/*** Definition for a binary tree node.* class TreeNode {*     val: number*     left: TreeNode | null*     right: TreeNode | null*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.left = (left===undefined ? null : left)*         this.right = (right===undefined ? null : right)*     }* }*/function constructMaximumBinaryTree(nums: number[]): TreeNode | null {const construct = (nums, left, right) => {if (left > right) return null;let best = left;for (let i = left + 1; i <= right; ++i) {if (nums[i] > nums[best]) {best = i;}}const node = new TreeNode(nums[best]);node.left = construct(nums, left, best - 1);node.right = construct(nums, best + 1, right);return node;}return construct(nums, 0, nums.length - 1);
};

2 ) 方案2：单调栈

/*** Definition for a binary tree node.* class TreeNode {*     val: number*     left: TreeNode | null*     right: TreeNode | null*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.left = (left===undefined ? null : left)*         this.right = (right===undefined ? null : right)*     }* }*/function constructMaximumBinaryTree(nums: number[]): TreeNode | null {const n = nums.length;const stack = [];const left = new Array(n).fill(-1);const right = new Array(n).fill(-1);const tree = new Array(n).fill(-1);for (let i = 0; i < n; ++i) {tree[i] = new TreeNode(nums[i]);while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {right[stack.pop()] = i;}if (stack.length) {left[i] = stack[stack.length - 1];}stack.push(i);}let root = null;for (let i = 0; i < n; ++i) {if (left[i] === -1 && right[i] === -1) {root = tree[i];} else if (right[i] === -1 || (left[i] !== -1 && nums[left[i]] < nums[right[i]])) {tree[left[i]].right = tree[i];} else {tree[right[i]].left = tree[i];}}return root;
};

3 ) 方案3：单调栈优化

/*** Definition for a binary tree node.* class TreeNode {*     val: number*     left: TreeNode | null*     right: TreeNode | null*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.left = (left===undefined ? null : left)*         this.right = (right===undefined ? null : right)*     }* }*/function constructMaximumBinaryTree(nums: number[]): TreeNode | null {const n = nums.length;const stack = [];const tree = new Array(n).fill(0);for (let i = 0; i < n; ++i) {tree[i] = new TreeNode(nums[i]);while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {tree[i].left = tree[stack[stack.length - 1]];stack.pop();}if (stack.length) {tree[stack[stack.length - 1]].right = tree[i];}stack.push(i);}return tree[stack[0]];
};

数据结构与算法之二叉树: LeetCode 654. 最大二叉树 (Ts版)

最大二叉树 https://leetcode.cn/problems/maximum-binary-tree/ 描述给定一个不重复的整数数组 nums 。最大二叉树可以用下面的算法从 nums 递归地构建: 创建一个根节点，其值为 nums 中的最大值递归地在最大值左边的子数组前缀上构建左子树递归地在最大值…...

编程日记 2025/6/3 15:31:30

学习记录：C++宏定义包含多条语句，使用注意事项

应该使用 do - while(0) 结构的情况在条件语句（如 if - else、switch - case）或循环语句（如 for、while、do - while）中使用宏： 当宏定义包含多条语句且会在上述语句中使用时，使用 do - while(0) 可确保…...

编程日记 2025/6/2 5:13:52

PHP 使用 Redis

PHP 使用 Redis PHP 是一种广泛使用的服务器端编程语言，而 Redis 是一个高性能的键值对存储系统。将 PHP 与 Redis 结合使用，可以为 Web 应用程序提供快速的读写性能和丰富的数据结构。本文将详细介绍如何在 PHP 中使用 Redis，包括安装、连接、基本操作以及一些高级应用。 …...

编程日记 2025/5/31 0:36:30

项目开发实践——基于SpringBoot+Vue3实现的在线考试系统(五)

文章目录一、学生管理模块功能实现1、添加学生功能实现1.1 页面设计1.2 前端功能实现1.3 后端功能实现1.4 效果展示2、学生管理功能实现2.1 页面设计2.2 前端功能实现2.3 后端功能实现2.3.1 后端查询接口实现2.3.2 后端编辑接口实现2.3.3 后端删除接口实现2.4 效果展示二、代码…...

编程日记 2025/6/2 0:01:38

下载并安装MySQL

在Linux系统上下载并安装数据库（以MySQL为例）的步骤如下： 一、下载MySQL 访问MySQL官网打开浏览器，访问MySQL的官方网站：https://www.mysql.com/。进入下载页面在MySQL官网首页，找到并点击“Downloads…...

编程日记 2025/5/29 15:33:30

【C++入门】详解（中）

目录 💕1.函数的重载 💕2.引用的定义 💕3.引用的一些常见问题 💕4.引用——权限的放大/缩小/平移 💕5. 不存在的空引用 💕6.引用作为函数参数的速度之快（代码体现） &#x1f4…...

编程日记 2025/6/3 8:20:08

计算机视觉算法实战——车道线检测

✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连✨ 车道线检测是计算机视觉领域的一个重要研究方向，尤其在自动驾驶和高级驾驶辅助…...

编程日记 2025/6/3 6:37:45

基于http协议的天气爬虫

该系统将基于目前比较流行的网络爬虫技术， 对网站上的天气数据进行查询分析， 最终使客户能够通过简单的操作， 快速， 准确的获取目标天气数据。主要包括两部分的功能， 第一部分是天气数据查询， 包括时间段数…...

编程日记 2025/6/3 7:23:29

自然语言处理基础：全面概述

自然语言处理基础：全面概述什么是NLP及其重要性、NLP的核心组件、NLU与NLG、NLU与NLG的集成、NLP的挑战以及NLP的未来自然语言处理（NLP）是人工智能（AI）中最引人入胜且具有影响力的领域之一。它驱动着我们日常使用的…...

编程日记 2025/5/27 5:36:45

软件架构考试基础知识 002：进程的状态与其切换

进程状态转换的说明在操作系统中，进程的状态表示其当前的执行情况和资源占用情况。进程状态的转换反映了操作系统如何管理和调度进程。以下是进程状态转换的说明： 1. 三态模型（Three-state Model） 三态模型是最基础的进程状态模…...

编程日记 2025/6/1 0:59:38

【Linux系列】Curl 参数详解与实践应用

💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。推荐:kwan 的首页,持续学…...

编程日记 2025/6/2 10:23:20

VsCode对Arduino的开发配置

ps：我的情况是在对esp32进行编译、烧录时，找不到按钮，无法识别Arduino文件，适合已经有ini文件的情况。 1.在vscode中安装拓展 2.打开设置，点击右上角，转到settings.json文件 3.复制以下代码并保存 {"…...

编程日记 2025/5/30 21:15:53

【Pandas】pandas Series rtruediv

Pandas2.2 Series Binary operator functions 方法描述Series.add()用于对两个 Series 进行逐元素加法运算Series.sub()用于对两个 Series 进行逐元素减法运算Series.mul()用于对两个 Series 进行逐元素乘法运算Series.div()用于对两个 Series 进行逐元素除法运算Series.true…...

编程日记 2025/6/3 3:56:36

VUE3 自定义指令的介绍

自定义指令的概述在 Vue 中，自定义指令是一种机制，允许开发者在模板中直接操作 DOM 元素，执行一些低级别的操作。Vue 提供了几个内置指令（如 v-if、v-for、v-model 等），但当我们需要一些特定功能时&#…...

编程日记 2025/6/1 20:18:13

安装redisDB 主节点 apt install redis-server修改配置 /etc/redis/redis.conf bind 0.0.0.0save "" # 禁止RDB持久化 #save 900 1 #save 300 10 #save 60 10000appendonly no # 禁止AOF持久化重启服务 systemctl restart redis-server从节点配置文件 bind 0.…...

编程日记 2025/6/3 10:22:59

【汇编】x86汇编编程寄存器资源心中有数

1. CPU状态及控制寄存器 TR，GDTR，LDTRcr0-cr3EFLAGS 等等 2. 业务计算寄存器（我起的名字） 业务寄存器用于访问内存、参数传递、数据传递、计算。段寄存器6个： cs，ds，es，ss&…...

编程日记 2025/5/31 7:03:34

一.项目课题＜基于TCP的文件传输协议实现＞

客户端代码需要cJSON.c文件和cJSON.h文件在这里插入代码片#include "myheadth.h" #include "myfun.h"#define TIME 10 int sockfd; void heartbeat(int signum) {cJSON* root cJSON_CreateObject();cJSON_AddStringToObject(root,"request"…...

编程日记 2025/6/3 10:36:17

【数据结构学习笔记】19：跳表（SkipList）

介绍跳表是一个能在 O ( n l o g n ) O(nlogn) O(nlogn)时间完成查找、插入、删除的数据结构，相比于树形结构优点就是很好写（所以也用于实现Redis ZSet）。其核心思想就是维护一个元素有序的，能随机提升索引层数的链表。最下面一…...

编程日记 2025/5/23 23:21:59

Cocos Creator 3.8 修改纹理像素值

修改的代码： import { _decorator, Component, RenderTexture, Sprite, Texture2D, ImageAsset, SpriteFrame, Vec2, gfx, director, log, math, v2 } from cc;const { ccclass, property } _decorator;ccclass(GradientTransparency) export class GradientTrans…...

编程日记 2025/6/3 17:27:03

【Linux】网络层

目录 IP协议协议头格式网段划分 2中网段划分的方式为什么要进行网段划分特殊的IP地址 IP地址的数量限制私有IP地址和公有IP地址路由 IP协议在通信时，主机B要把数据要给主机C，一定要经过一条路径选择，为什么经过路由器G后&…...

编程日记 2025/6/3 22:13:09

单片机Day1

目录一.什么是单片机？ 二.单片机的组成三.封装形式四.优势五.分类通用型： 专用型： 按处理的二进制位可以分为： 六.应用： 七.发展趋势 1.增加CPU的数据总线宽度。 2.存储器的发展。 3.片内1/0的改进 …...

编程日记 2025/6/1 10:40:51

django基于 Python 的考研学习系统的设计与实现

以下是对Django基于Python的考研学习系统的设计与实现： 一、系统概述 Django基于Python的考研学习系统是一个为考研学子提供一站式学习辅助的平台。它整合了丰富的学习资源、学习计划制定、学习进度跟踪以及交流互动等功能，旨在满足考生在备考过程中的…...

编程日记 2025/6/4 10:57:01

openCvSharp 计算机视觉图片找茬

一、安装包 <PackageReference Include"OpenCvSharp4" Version"4.10.0.20241108" /> <PackageReference Include"OpenCvSharp4.runtime.win" Version"4.10.0.20241108" /> 二、准备两张图片三、编写代码 using OpenCv…...

编程日记 2025/5/30 22:18:22

深入学习 Python 爬虫：从基础到实战

深入学习 Python 爬虫：从基础到实战前言 Python 爬虫是一个强大的工具，可以帮助你从互联网上抓取各种数据。无论你是数据分析师、机器学习工程师，还是对网络数据感兴趣的开发者，爬虫都是一个非常实用的技能。在本文中&#xff…...

编程日记 2025/6/1 5:55:02

【Web安全】SQL 注入攻击技巧详解：UNION 注入（UNION SQL Injection）

【Web安全】SQL 注入攻击技巧详解：UNION 注入（UNION SQL Injection） 引言 UNION注入是一种利用SQL的UNION操作符进行注入攻击的技术。攻击者通过合并两个或多个SELECT语句的结果集，可以获取数据库中未授权的数据。这种注入技术要…...

编程日记 2025/6/2 3:42:22

【DAPM杂谈之一】DAPM作用与内核文档解读

本文主要分析DAPM的设计与实现内核的版本是：linux-5.15.164，下载链接： Linux内核下载主要讲解有关于DAPM相关的知识，会给出一些例程并分析内核如何去实现的 /****************************************************************…...

编程日记 2025/6/2 10:20:45

计算机网络之---防火墙与入侵检测系统(IDS)

防火墙与入侵检测系统(IDS) 防火墙（Firewall） 和入侵检测系统（IDS, Intrusion Detection System） 都是网络安全的关键组件，但它们的作用、功能和工作方式有所不同。防火墙防火墙是网络安全的一种设备或软件&#…...

编程日记 2025/6/3 23:49:12

HTML中meta的用法

学习网络空间安全专业，每个人有每个人的学法和选择。不论他选择什么，哪都是他自己的选择，这就是大多数视频教学的博主教学的步骤都不同原因之一。有人选择丢掉大部分理论直接学习网安，而我，选择了捡起大部分理论学习网…...

编程日记 2025/5/30 18:00:06

前端学习-事件流，事件捕获，事件冒泡以及阻止冒泡以及相应案例（二十八）

目录前言事件流与两个阶段说明说明事件捕获目标说明事件冒泡目标事件冒泡概念简单理解阻止冒泡目标语法注意综合示例代码总结前言梳洗罢，独倚望江楼。过尽千帆皆不是，斜晖脉脉水悠悠。肠断白蘋洲事件流与两个阶段说明…...

编程日记 2025/6/1 11:56:45

国产OS移植工业物联网OPC-UA协议

国家对于工业互联网、基础软件等关键领域的重视程度不断提升，为工业领域的硬件与软件国产化提供了坚实的政策保障。国产操作系统对工业物联网的一些重要领域的适配支持一直在推进。本次通过国产UOS系统移植测试OPC-UA协议。 1、OPC UA通信协议 OPC UA 协议&#xf…...

编程日记 2025/5/30 15:50:56

第25章汇编语言--- 信号量与互斥锁

信号量（Semaphore）和互斥锁（Mutex，全称Mutual Exclusion Object）是两种用于管理对共享资源的访问的同步机制。它们在多线程或多进程编程中非常重要，可以确保同一时间只有一个线程或进程能够访问特定的资源&…...

编程日记 2025/6/1 14:10:58

写个自己的vue-cli

写个自己的vue-cli 1.插件代码2. 发布流程3. 模板代码讲解3.1 vue2模板的运行流程:3.2 vue3模板的运行流程: 1.插件代码写一个自己的vue-cli插件插件地址：插件地址流程： 实现简单版 vue-cli 步骤文档1. 项目初始化 - 创建项目文件夹 qsl-vue-cli - …...

编程日记 2025/6/4 15:47:07

使用new Vue创建Vue 实例并使用$mount挂载到元素上(包括el选项和$mount区别)

new Vue({...}) 是创建一个新的 Vue 实例的方式。你可以通过传递一个选项对象来配置这个实例。常见的选项包括： •data：定义组件的数据属性。 •el：指定 Vue 实例应该挂载到哪个 DOM 元素上（通常是一个选择器字符串，如…...

编程日记 2025/6/3 6:40:44

【理论】测试框架体系TDD、BDD、ATDD、MBT、DDT介绍

一、测试框架是什么测试框架是一组用于创建和设计测试用例的指南或规则。框架由旨在帮助 QA 专业人员更有效地测试的实践和工具的组合组成。这些指南可能包括编码标准、测试数据处理方法、对象存储库、存储测试结果的过程或有关如何访问外部资源的信息。 A testing framewo…...

编程日记 2025/6/4 10:49:00

机器学习全流程解析：数据导入到服务上线全阶段介绍

目录 1. 数据导入 2. 数据预处理 3. 超参数搜索与优化 4. 模型训练 5. 模型评估 6. 模型压缩与优化 7. 模型注册与版本管理 8. 服务上线与部署总结 1. 数据导入数据源：数据库、文件系统、API等。数据格式：CSV、JSON、SQL 数据库表、Parquet …...

编程日记 2025/5/31 9:19:50

shell脚本练习

1、shell 脚本写出检测 /tmp/size.log 文件如果存在显示它的内容，不存在则创建一个文件将创建时间写入。 if [ -f /tmp/size.log ];thencat /tmp/size.logelsestat exist.sh | awk -F: "NR5" > /tmp/size.logfi 2、写一个 shel1 脚本,实现批量添加…...

编程日记 2025/5/31 4:42:09

金山WPS Android面试题及参考答案

说说你所知道的所有集合？并阐述其内部实现。在 Android 开发（Java 语言基础上）中有多种集合。首先是 List 集合，主要包括 ArrayList 和 LinkedList。 ArrayList 是基于数组实现的动态数组。它的内部有一个数组来存储元素，当添加元素时，如果数组容量不够，会进行扩容操作…...

编程日记 2025/5/29 10:10:43

分类模型为什么使用交叉熵作为损失函数

推导过程让推理更有体感，进行下面假设： 假设要对猫、狗进行图片识别分类假设模型输出 y y y，是一个几率，表示是猫的概率训练资料如下： x n x^n xn类别 y ^ n \widehat{y}^n y n x 1 x^1 x1猫1 x 2 x^2 x2猫1 x …...

编程日记 2025/6/2 14:55:24

高等数学学习笔记 ☞ 单调性、凸凹性、极值、最值、曲率

1. 单调性 1. 单调性定义：设函数在区间上有定义，对于区间上任意两点，若： ①：当时，恒有，则称函数在区间上单调递增。 ②：当时，恒有，则称函数在区间上单调递减…...

编程日记 2025/6/3 1:50:59

【操作系统】详解操作系统及其结构

考察频率难度40%--60%⭐⭐ 这又是一类面试考察题，是关于操作系统的一些概念问题，很少会单独拎出来作为一个问题进行提问，但却是必须要掌握的。因为如果这个你不会，其他的问题就已经没有回答的必要了。什么是操作系统&#xff1…...

编程日记 2025/6/2 8:49:07

primitive 的 Appearance编写着色器材质

import { nextTick, onMounted, ref } from vue import * as Cesium from cesium import gsap from gsaponMounted(() > { ... })// 1、创建矩形几何体，Cesium.RectangleGeometry：几何体，Rectangle：矩形 let rectGeometry new…...

编程日记 2025/5/30 8:34:53

自动化测试框架搭建-接口数据结构设计

目的确认数据库如何保存接口数据，既有扩展性，数据又全又好用根据用途设计数据库字段区分环境：可以明确当前接口自动化用例，是在哪个环境需要执行的模块：微服务架构，不同测试同学负责不同的模块&…...

编程日记 2025/6/3 8:22:57

Python自学 - 使用自定义异常

<< 返回目录 1 Python自学 - 使用自定义异常在Python中， 不仅可以使用内置异常，用户还可以创建自己的异常。自定义异常需要继承自Exception类或其子类，如下是一个自定义异常示例： 示例1：一个简单的自定义异常…...

编程日记 2025/6/2 10:36:51

微信小程序-Docker+Nginx环境配置业务域名验证文件

在实际开发或运维工作中，我们时常需要在 Nginx 部署的服务器上提供一个特定的静态文件，用于域名验证或第三方平台验证。若此时使用 Docker 容器部署了 Nginx，就需要将该验证文件正确地映射（挂载）到容器中，并…...

编程日记 2025/6/4 15:30:00

“AI智能服务平台系统，让生活更便捷、更智能

大家好，我是资深产品经理老王，今天咱们来聊聊一个让生活变得越来越方便的高科技产品——AI智能服务平台系统。这个系统可是现代服务业的一颗璀璨明珠，它究竟有哪些魅力呢？下面我就跟大家伙儿闲聊一下。一、什么是AI智能服务平台系…...

编程日记 2025/6/4 1:29:22

【PPTist】插入形状、插入图片、插入图表

一、插入形状插入形状有两种情况，一种是插入固定的形状， 一种是插入自定义的形状。插入固定的形状时，跟上一篇文章绘制文本框是一样一样的，都是调用的 mainStore.setCreatingElement() 方法，只不多传的类型不一…...

编程日记 2025/6/3 13:44:29

云集电商：数据库的分布式升级实践｜OceanBase案例

电商行业对数据库有哪些需求云集电商作为一家传统电商企业，业务涵盖了美妆个护、服饰、水果生鲜、健康保健等多个领域，在创立四年后在纳斯达克上市（股票代码：YJ）。与京东、淘宝、拼多多等电商平台不同，云…...

编程日记 2025/6/3 19:26:58

OOM排查思路

K8S 容器的云原生生态，改变了服务的交付方式，自愈能力和自动扩缩等功能简直不要太好用。有好的地方咱要夸，不好的地方咱也要说，真正的业务是部署于容器内部，而容器之外，又有一逻辑层 Pod 。对于容器和…...

编程日记 2025/6/4 12:51:51

Q_OBJECT宏报错的问题

在Qt中继承QObject，并且加上Q_OBJECT宏，有时候会报错，比如我的错误： error: debug/httpmgr.o:httpmgr.cpp:(.rdata$.refptr._ZTV7HttpMgr[.refptr._ZTV7HttpMgr]0x0): undefined reference to vtable for HttpMgr 意思是没有虚…...

编程日记 2025/6/2 5:33:13

iOS - 关联对象

详细总结 Objective-C 的关联对象功能： 1. 基本使用 // 1. 设置关联对象 objc_setAssociatedObject(id object, const void *key, id value, objc_AssociationPolicy policy);// 2. 获取关联对象 id objc_getAssociatedObject(id object, const void *key);// 3. …...

编程日记 2025/6/4 17:12:19

最大二叉树

描述

示例 1

示例 2

提示

Typescript 版算法实现

相关文章：