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

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

最大二叉树

  • 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 递归地构建: 创建一个根节点&#xff0c;其值为 nums 中的最大值递归地在最大值 左边 的 子数组前缀上 构建左子树递归地在最大值…...

Linux 容器漏洞

定义&#xff1a;Linux 容器漏洞是指在容器技术&#xff08;如 Docker、LXC 等&#xff09;运行环境中存在的安全弱点。这些漏洞可能存在于容器镜像本身、容器运行时&#xff08;如 runc&#xff09;、容器编排工具&#xff08;如 Kubernetes&#xff09;或者容器与主机之间的交…...

file与io流(1)

-1- java.io.File类的使用 &#xff08;1&#xff09; 概述 File类及本章下的各种流&#xff0c;都定义在java.io包下。一个File对象代表硬盘或网络中可能存在的一个文件或者文件目录&#xff08;俗称文件夹&#xff09;&#xff0c;与平台无关。&#xff08;体会万事万物皆…...

忘记了PDF文件的密码,怎么办?

PDF文件可以加密&#xff0c;大家都不陌生&#xff0c;并且大家应该也都知道PDF文件有两种密码&#xff0c;一个打开密码、一个限制编辑密码&#xff0c;因为PDF文件设置了密码&#xff0c;那么打开、编辑PDF文件就会受到限制。忘记了PDF密码该如何解密&#xff1f; PDF和offi…...

Linux权限管理(用户和权限之间的关系)

Linux系列 文章目录 Linux系列一、Linux下用户类型二、普通权限的基本概念2.1、Linux中权限的类别2.2、Linux中权限对应的三种身份2.3、文件权限的标识 三、文件权限设置四、修改文件属主和属组4.1、chown修改文件的属主4.2、修改所属组 五、文件掩码六、目录权限 一、Linux下用…...

Python Selenium库入门使用,图文详细。附网页爬虫、web自动化操作等实战操作。

文章目录 前言1 创建conda环境安装Selenium库2 浏览器驱动下载&#xff08;以Chrome和Edge为例&#xff09;3 基础使用&#xff08;以Chrome为例演示&#xff09;3.1 与浏览器相关的操作3.1.1 打开/关闭浏览器3.1.2 访问指定域名的网页3.1.3 控制浏览器的窗口大小3.1.4 前进/后…...

【Uniapp-Vue3】使用defineExpose暴露子组件的属性及方法

如果我们想要让父组件访问到子组件中的变量和方法&#xff0c;就需要使用defineExpose暴露&#xff1a; defineExpose({ 变量 }) 子组件配置 父组件配置 父组件要通过onMounted获取到子组件的DOM 传递多个属性和方法 子组件 父组件...

【多模态LLM】英伟达NVLM多模态大模型训练细节和数据集

前期笔者介绍了OCR-free的多模态大模型&#xff0c;可以参考&#xff1a;【多模态&文档智能】OCR-free感知多模态大模型技术链路及训练数据细节&#xff0c;其更偏向于训练模型对于密集文本的感知能力。本文看一看英伟达出品的多模态大模型NVLM-1.0系列&#xff0c;虽然暂未…...

HTTP详解——HTTP基础

HTTP 基本概念 HTTP 是超文本传输协议 (HyperText Transfer Protocol) 超文本传输协议(HyperText Transfer Protocol) HTTP 是一个在计算机世界里专门在 两点 之间 传输 文字、图片、音视频等 超文本 数据的 约定和规范 1. 协议 约定和规范 2. 传输 两点之间传输&#xf…...

MySQL教程之:输入查询

如上一节所述&#xff0c;确保您已连接到服务器。这样做本身不会选择任何要使用的数据库&#xff0c;但没关系。在这一点上&#xff0c;了解一下如何发出查询比直接创建表、加载数据和从中检索数据更重要。本节介绍输入查询的基本原则&#xff0c;使用几个查询&#xff0c;您可…...

docker+ffmpeg+nginx+rtmp 拉取摄像机视频

1、构造程序容器镜像 app.py import subprocess import json import time import multiprocessing import socketdef check_rtmp_server(host, port, timeout5):try:with socket.create_connection((host, port), timeout):print(f"RTMP server at {host}:{port} is avai…...

不同音频振幅dBFS计算方法

1. 振幅的基本概念 振幅是描述音频信号强度的一个重要参数。它通常表示为信号的幅度值&#xff0c;幅度越大&#xff0c;声音听起来就越响。为了更好地理解和处理音频信号&#xff0c;通常会将振幅转换为分贝&#xff08;dB&#xff09;单位。分贝是一个对数单位&#xff0c;能…...

【17. 电话号码的字母组合 中等】

题目&#xff1a; 给定一个仅包含数字 2-9 的字符串&#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下&#xff08;与电话按键相同&#xff09;。注意 1 不对应任何字母。 示例 1&#xff1a; 输入&#xff1a;digits “23”…...

数据结构初阶---排序

一、排序相关概念与运用 1.排序相关概念 排序&#xff1a;所谓排序&#xff0c;就是使一串记录&#xff0c;按照其中的某个或某些关键字的大小&#xff0c;递增或递减的排列起来的操作。 稳定性&#xff1a;假定在待排序的记录序列中&#xff0c;存在多个具有相同的关键字的…...

【从0-1实现一个前端脚手架】

目录 介绍为什么需要脚手架&#xff1f;一个脚手架应该具备哪些功能&#xff1f; 脚手架实现初始化项目相关依赖实现脚手架 发布 介绍 为什么需要脚手架&#xff1f; 脚手架本质就是一个工具&#xff0c;作用是能够让使用者专注于写代码&#xff0c;它可以让我们只用一个命令…...

AI文章管理系统(自动生成图文分发到分站)

最近帮一个网上的朋友做了一套AI文章生成系统。他的需求是这样&#xff1a; 1、做一个服务端转接百度文心一言的生成文章的API接口。 2、服务端能注册用户&#xff0c;用户在服务端注册充值后可以获取一个令牌&#xff0c;这个令牌填写到客户端&#xff0c;客户端就可以根据客…...

【Leetcode 每日一题】3270. 求出数字答案

问题背景 给你三个 正 整数 n u m 1 num_1 num1​&#xff0c; n u m 2 num_2 num2​ 和 n u m 3 num_3 num3​。 数字 n u m 1 num_1 num1​&#xff0c; n u m 2 num_2 num2​ 和 n u m 3 num_3 num3​ 的数字答案 k e y key key 是一个四位数&#xff0c;定义如下&…...

基于单片机的无线气象仪系统设计(论文+源码)

1系统方案设计 如图2.1所示为无线气象仪系统设计框架。系统设计采用STM32单片机作为主控制器&#xff0c;结合DHT11温湿度传感器、光敏传感器、BMP180气压传感器、PR-3000-FS-N01风速传感器实现气象环境的温度、湿度、光照、气压、风速等环境数据的检测&#xff0c;并通过OLED1…...

【数据库】Mysql精简回顾复习

一、概念 数据库&#xff08;DB&#xff09;&#xff1a;数据存储的仓库数据库管理系统&#xff08;DBMS&#xff09;&#xff1a;操纵和管理数据库的大型软件SQL&#xff1a;操作关系型数据库的编程语言&#xff0c;是一套标准关系型数据库&#xff08;RDBMS&#xff09;&…...

深入理解 HTTP 的 GET、POST 方法与 Request 和 Response

HTTP 协议是构建 Web 应用的基石&#xff0c;GET 和 POST 是其中最常用的请求方法。无论是前端开发、后端开发&#xff0c;还是接口测试&#xff0c;对它们的深入理解都显得尤为重要。在本文中&#xff0c;我们将介绍 GET 和 POST 方法&#xff0c;以及 Request 和 Response 的…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

深入理解Optional:处理空指针异常

1. 使用Optional处理可能为空的集合 在Java开发中&#xff0c;集合判空是一个常见但容易出错的场景。传统方式虽然可行&#xff0c;但存在一些潜在问题&#xff1a; // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

用鸿蒙HarmonyOS5实现中国象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...

面试高频问题

文章目录 &#x1f680; 消息队列核心技术揭秘&#xff1a;从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"&#xff1f;性能背后的秘密1.1 顺序写入与零拷贝&#xff1a;性能的双引擎1.2 分区并行&#xff1a;数据的"八车道高速公路"1.3 页缓存与批量处理…...

xmind转换为markdown

文章目录 解锁思维导图新姿势&#xff1a;将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件&#xff08;ZIP处理&#xff09;2.解析JSON数据结构3&#xff1a;递归转换树形结构4&#xff1a;Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...