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

【LeetCode 热题100】二叉树构造题精讲:前序 + 中序建树 有序数组构造 BST(力扣105 / 108)(Go语言版)

🌱 二叉树构造题精讲:前序 + 中序建树 & 有序数组构造 BST

本文围绕二叉树的两类构造类题目展开解析:

    1. 从前序与中序遍历序列构造二叉树
    1. 将有序数组转换为二叉搜索树

我们将从「已知遍历构造树」和「平衡构造 BST」两个角度,拆解树结构的构建逻辑,彻底吃透构造题型。


📌 题目一:105. 从前序与中序遍历序列构造二叉树

📝 题目描述

给定两棵树的遍历序列:

  • preorder(前序遍历):根 -> 左 -> 右
  • inorder(中序遍历):左 -> 根 -> 右

请根据这两种遍历构造原始二叉树。


🔍 解题思路

核心思路:

  1. 前序遍历的第一个元素一定是根节点;
  2. 在中序遍历中找到这个根节点的位置,可以确定左右子树的元素范围;
  3. 递归构造左右子树。

✅ 解法:递归构造

func buildTree(preorder []int, inorder []int) *TreeNode {inMap := map[int]int{}for i, val := range inorder {inMap[val] = i}var build func(pl, pr, il, ir int) *TreeNodebuild = func(pl, pr, il, ir int) *TreeNode {if pl > pr || il > ir {return nil}rootVal := preorder[pl]root := &TreeNode{Val: rootVal}idx := inMap[rootVal]leftSize := idx - ilroot.Left = build(pl+1, pl+leftSize, il, idx-1)root.Right = build(pl+leftSize+1, pr, idx+1, ir)return root}return build(0, len(preorder)-1, 0, len(inorder)-1)
}

📘 思路详解

  • 使用 inMap 来快速定位中序中某个值的位置,避免每次线性搜索;
  • 用索引控制遍历范围,不要切片传参,会影响性能
  • 每次递归缩小当前处理的 preorder 和 inorder 区间。

⚠️ 注意事项:

  • preorder[pl] 是当前子树的根节点;
  • 左子树的大小为 idx - il
  • 左右子树递归时注意索引边界不要写错。

📌 题目二:108. 将有序数组转换为二叉搜索树

📝 题目描述

给你一个升序排序的整数数组,请你将其转化为一棵高度平衡的二叉搜索树(BST)


🔍 解题思路

关键点:

  • 数组有序 → 可用中间元素构建根节点;
  • 左边递归为左子树,右边递归为右子树;
  • 中间元素选择策略:可以取中间偏左或偏右均可。

✅ 解法:递归 + 中点分割

func sortedArrayToBST(nums []int) *TreeNode {var build func(left, right int) *TreeNodebuild = func(left, right int) *TreeNode {if left > right {return nil}mid := (left + right) / 2root := &TreeNode{Val: nums[mid]}root.Left = build(left, mid-1)root.Right = build(mid+1, right)return root}return build(0, len(nums)-1)
}

💭 思维补充

  • 二叉搜索树要求:左 < 根 < 右;
  • 高度平衡树要求:每个节点左右子树高度差不超过 1;
  • 因此「中间作为根」是构造平衡 BST 的最优策略。

🧠 总结 & 对比

题目类型输入输出核心操作
105构造普通二叉树前序 + 中序遍历树结构递归 + 分治(索引控制)
108构造平衡 BST有序数组BST 树结构递归 + 二分中点

🎯 通用构造套路小结:

  1. 明确根节点从何而来(前序 or 中点);
  2. 找到左右子树的边界
  3. 索引控制子问题的范围
  4. 构建节点,递归处理左右子树;
  5. 特别注意边界条件与 base case

✨ 进阶思考

  • 如果输入是 中序 + 后序,你还能反推出树吗?
  • 如果输入是 BST + 任意遍历,你能判断树结构吗?

这些问题都是构造类题目的常见变体,建议从这两题出发逐步拓展思维路径。


下一篇将带你探索搜索树相关的问题,从验证 BST 到查找第 K 小元素,一起掌握搜索树的价值!

如有帮助,欢迎点赞收藏,更多结构题内容持续更新中 🧠💡


相关文章:

【LeetCode 热题100】二叉树构造题精讲:前序 + 中序建树 有序数组构造 BST(力扣105 / 108)(Go语言版)

&#x1f331; 二叉树构造题精讲&#xff1a;前序 中序建树 & 有序数组构造 BST 本文围绕二叉树的两类构造类题目展开解析&#xff1a; 从前序与中序遍历序列构造二叉树 将有序数组转换为二叉搜索树 我们将从「已知遍历构造树」和「平衡构造 BST」两个角度&#xff0c;拆…...

开源语音文本自动对齐模型:Llama-OuteTTS-1.0-1B

OuteTTS 1.0 介绍与使用指南 1. 重要采样考虑 重复惩罚机制&#xff1a;OuteTTS 1.0 要求对最近的64个token应用重复惩罚&#xff0c;而不是对整个上下文窗口。对整个上下文窗口进行惩罚会导致输出质量下降。推荐工具&#xff1a;llama.cpp 和 EXL2 提供了可靠的输出质量&…...

基于SpringBoot的电影订票系统(源码+数据库+万字文档+ppt)

504基于SpringBoot的电影订票系统&#xff0c;系统包含两种角色&#xff1a;管理员、用户主要功能如下。 【用户功能】 首页&#xff1a;浏览系统电影动态。 资讯信息&#xff1a;获取有关电影行业的新闻和资讯。 电影信息&#xff1a;查看电影的详细信息和排片情况。 公告信…...

基于SpringBoot汽车零件商城系统设计和实现(源码+文档+部署讲解)

技术范围&#xff1a;SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容&#xff1a;免费功能设计、开题报告、任务书、中期检查PPT、系统功能实现、代码编写、论文编写和辅导、论文…...

Python数据可视化:从脚本到海报级图表

Python数据可视化:从脚本到海报级图表 引言 在数据分析和科学计算领域,Python 是一种强大且灵活的工具。本文将带您了解如何使用 Python 进行数据可视化,从简单的脚本到生成高质量的海报级图表。我们将重点介绍如何使用 Matplotlib 库来创建、保存和优化图表,以便在各种场…...

使用Java截取MP4文件图片的技术指南

在多媒体处理中&#xff0c;从视频文件中截取图片是一个常见的需求。本文将详细介绍如何使用Java结合FFmpeg实现从MP4文件中截取图片的功能。我们将通过几种不同的方法来实现这一目标&#xff0c;包括直接调用FFmpeg命令行工具、使用JavaCV库以及使用JAVE库。 环境准备 在开始…...

C++(初阶)(十一)——list

十一&#xff0c;list 带头循环双向链表。 遍历方式&#xff1a;迭代器&#xff0c;不再支持operate[]&#xff0c;operate[]适用于底层是数组的结构。 remove删除值&#xff0c;如果有多个相同的值&#xff0c;都会删除。 接口介绍 下面会介绍list的一些接口 构造 构造…...

leetcode 139. Word Break

这道题用动态规划解决。 class Solution { public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet;for(string& word:wordDict){wordSet.insert(word);}int s_len s.size();//s的下标从1开始起算&#xff0c;dp[j]…...

5.1、深度剖析 docker run 命令:原理阐释与数据持久化实践探究

5.1、深度剖析 docker run 命令:原理阐释与数据持久化实践探究 1、更换国内yum源2、更换国内docker源3、卸载旧版docker4、docker安装5、镜像加速器6、镜像下载7、docker run命令交互式启动-it非交互式后台运行其他参数8、持久化存储目录挂载数据卷挂载数据同步1、更换国内yum…...

【AI大模型】大模型RAG技术Langchain4j 核心组件深入详解

目录 一、前言 二、Langchain4j概述 2.1 Langchain4j 是什么 2.2 Langchain4j 主要特点 2.3 Langchain4j 核心组件 2.4 Langchain4j 核心优势 三、Langchanin4j组件应用实战 3.1 前置准备 3.1.1 导入如下依赖 3.1.2 获取apikey 3.1.3 获取官方文档 3.2 聊天组件 3.…...

【Flink运行时架构】重要概念

前面我们讲了Flink运行时的核心组件和提交流程&#xff0c;但有些细节需要进一步的思考&#xff0c;一个具体的作业是怎样从编写的代码转换成TaskManager可以执行的任务的呢&#xff1f;JobManager在收到提交的作业之后&#xff0c;又是如何确定总共有多少任务、需要配置多少资…...

oracle命令上下左右键无法使用如何解决?

1、问题如图 2、解决办法 (1) 安装readline yum -y install readline* &#xff08;2&#xff09;安装 rlwrap ##下载 wget http://files.cnblogs.com/files/killkill/rlwrap-0.30.tar.gz.zip ##解压 tar -xzvf rlwrap-0.30.tar.gz.zip ##编译安装 ./configure make &&…...

[文献阅读] chinese-roberta Pre-Training With Whole Word Masking for Chinese BERT

文献信息&#xff1a;Pre-Training With Whole Word Masking for Chinese BERT | IEEE Journals & Magazine | IEEE Xplore 哈工大和科大讯飞联合发表的用于中文NLP任务的基于BERT的改进模型&#xff0c;在中文NLP任务取得了最先进的性能。 摘要 原本的BERT使用随机掩蔽的…...

QML ListView 与 C++ 模型交互

在 Qt 中&#xff0c;QML 的 ListView 可以与 C 模型进行交互&#xff0c;这是实现复杂数据展示和业务逻辑的常见方式。以下是几种主要的交互方法&#xff1a; 1. 使用 QAbstractItemModel 派生类 这是最强大和灵活的方式&#xff0c;适合复杂数据结构。 C 端实现 cpp // …...

使用SSH解决在IDEA中Push出现403的问题

错误截图&#xff1a; 控制台日志&#xff1a; 12:15:34.649: [xxx] git -c core.quotepathfalse -c log.showSignaturefalse push --progress --porcelain master refs/heads/master:master fatal: unable to access https://github.com/xxx.git/: The requested URL return…...

MacOs下解决远程终端内容复制并到本地粘贴板

常常需要在服务器上捣鼓东西&#xff0c;同时需要将内容复制到本地的需求。 1-内容是在远程终端用vim打开&#xff0c;如何用vim的类似指令达到快速复制到本地呢&#xff1f; 假设待复制的内容&#xff1a; #include <iostream> #include <cstring> using names…...

修改idea/android studio等编辑器快捷注释从当前行开头的反人类行为

不知道什么时候开始&#xff0c;idea编辑的快捷注释开始从当前行开头出现了&#xff0c;显得实在是难受&#xff0c;我只想让在当前行代码的部份开始缩进两个字符开始&#xff0c;这样才会显得更舒服。不知道有没有强迫症的猴子和我一样&#xff0c;就像下面的效果&#xff1a;…...

密码加密方式

密码加密方式全面解析 密码安全是系统安全的第一道防线&#xff0c;以下是主流的密码加密技术分类和实现方式&#xff1a; 一、基础加密方式 1. 对称加密 特点&#xff1a;加密解密使用相同密钥 AES (Advanced Encryption Standard) 密钥长度&#xff1a;128/192/256位示例…...

Python10天突击--Day 2: 实现观察者模式

以下是 Python 实现观察者模式的完整方案&#xff0c;包含同步/异步支持、类型注解、线程安全等特性&#xff1a; 1. 经典观察者模式实现 from abc import ABC, abstractmethod from typing import List, Anyclass Observer(ABC):"""观察者抽象基类""…...

【C#】.NET 8适配器模式实战:用C#实现高可用系统集成与接口桥接艺术

系统集成挑战与适配器模式的价值 当需要整合不同架构或API的系统时&#xff0c;接口兼容性问题往往成为拦路虎。**适配器设计模式&#xff08;Adapter Pattern&#xff09;**通过转换接口形态&#xff0c;完美解决这种不兼容性问题。本文将通过C# .NET 8实战演示适配器模式的基…...

方案精读:51页 财政数据信息资源目录数据标准存储及大数据资产化规划方案【附全文阅读】

该方案聚焦财政数据信息资源管理,适用于财政部门工作人员、数据管理与分析人员以及关注财政大数据应用的相关人士。 方案旨在构建财政数据资源目录,推动大数据在财政领域的应用与落地。整体规划上,以 “金财工程” 应用支撑平台为基础,建立省、市、县三级目录体系,遵循相关…...

【CVE-2024-7881】ARM CPU漏洞安全通告

安全之安全(security)博客目录导读 目录 一、概述 二、CVE详情 三、受影响产品 四、修复建议 五、致谢 六、版本历史 一、概述 基于Arm架构的部分CPU中发现一个安全问题&#xff1a;非特权上下文可能触发数据内存依赖型预取引擎&#xff08;data memory-dependent pref…...

idea中提高编译速度研究

探索过程&#xff1a; 有三种情况&#xff1a; 第一种&#xff1a; idea中用eclipse编译器编译springboot项目&#xff0c;然后debug启动Application报错找不到类。 有待继续研究。 第二种&#xff1a; idea中用javac编译器编译springboot项目&#xff0c;重新构建用时&a…...

基于Yocto构建Ubuntu 24.04 ARM64 Qt工具链

以下是基于Yocto构建Ubuntu 24.04 ARM64 Qt工具链的完整方案&#xff0c;综合多篇技术文档整理而成&#xff1a; 一、系统环境准备 Ubuntu基础系统‌ 建议选择Ubuntu 24.04 LTS服务器版或桌面版&#xff0c;需满足至少300GB磁盘空间和16GB内存‌ 若使用ARM64架构主机可直接运…...

如何使用阿里云邮件推送免费群发邮件

最近一直想利用自己的阿里云账号开一个邮件推送服务&#xff0c;同时还可以用python来实现邮件群发&#xff0c;之前没有成功&#xff0c;今天又尝试了一次终于成功了&#xff0c;现将过程记录如下&#xff0c;也便于网友们少走弯路。 一、申请阿里云账号 阿里云注册可以用淘…...

利用 Genspark 和 AI IDE 一键配置 Java 开发环境

以下是以 CSDN 博客风格撰写的文章&#xff0c;基于你提到的“利用 Genspark 和 AI IDE 实现 Java 环境一键配置”的流程。文章结构清晰&#xff0c;内容详实&#xff0c;符合 CSDN 技术博客的常见风格&#xff0c;包含标题、简介、目录、正文、代码示例和总结。 利用 Genspark…...

【软考系统架构设计师】计算机网络知识点

1、 TCP/IP协议族 2、 数据链路层 解决三个基本问题&#xff1a; 封装成帧&#xff08;在⼀段数据的前后分别添加首部和尾部&#xff09; 透明传输&#xff08;发送⽅&#xff1a;若数据部分出现帧开始符或者帧结束符&#xff0c;会在其前面加转义字符&#xff1b;接收⽅&…...

RFID技术概览

一、RFID技术定义 RFID&#xff08;Radio Frequency Identification&#xff0c;射频识别&#xff09; 是一种通过无线电信号识别目标对象并获取相关数据的非接触式自动识别技术。它利用射频信号的空间耦合&#xff08;电感或电磁耦合&#xff09;实现无物理接触的信息传递与目…...

中间件--ClickHouse-2--OLAP和OLTP

OLAP&#xff08;Online Analytical Processing&#xff0c;联机分析处理&#xff09;和OLTP&#xff08;Online Transaction Processing&#xff0c;联机事务处理&#xff09;是两种不同类型的数据处理系统&#xff0c;它们分别针对不同的应用场景和需求。 1、OLTP&#xff0…...

使用ADB工具分析Android应用崩溃原因:以闪动校园为例

使用adb工具分析模拟器或手机里app出错原因以闪动校园为例 使用ADB工具分析Android应用崩溃原因&#xff1a;以闪动校园为例 前言 应用崩溃是移动开发中常见的问题&#xff0c;尤其在复杂的Android生态系统中&#xff0c;找出崩溃原因可能十分棘手。本文将以流行的校园应用&q…...

C++双链表介绍及实现

双链表详解 1. 基本概念 双链表&#xff08;双向链表&#xff09;​ 是一种链式数据结构&#xff0c;每个节点包含两个指针&#xff1a; ​前驱指针&#xff08;pre&#xff09;​&#xff1a;指向直接前驱节点​后继指针&#xff08;next&#xff09;​&#xff1a;指向直接…...

推流265视频,网页如何支持显示265的webrtc

科技发展真快&#xff0c;以前在网页上&#xff08;一般指谷歌浏览器&#xff09;&#xff0c;要显示265的视频流&#xff0c;都是很鸡肋的办法&#xff0c;要么转码&#xff0c;要么用很慢的hls&#xff0c;体验非常不好&#xff0c;而今谷歌官方最新的浏览器已经支持265的web…...

linux多线(进)程编程——(6)共享内存

前言 话说进程君的儿子经过父亲点播后就开始闭关&#xff0c;它想要开发出一种全新的传音神通。他想&#xff0c;如果两个人的大脑生长到了一起&#xff0c;那不是就可以直接知道对方在想什么了吗&#xff0c;这样不是可以避免通过语言传递照成的浪费吗&#xff1f; 下面就是它…...

Allpairs工具下载及操作流程(联动Deepseek)

目录 一、Allpairs工具下载及操作流程二、Allpairs工具使用易错问题 Allpairs工具产生的原因 Allpairs工具的产生源于软件测试领域对高效组合测试方法的迫切需求&#xff0c;其核心目标是解决传统测试方法在多因素组合场景下用例数量爆炸和测试效率低下的问题。 一、Allpairs工…...

wkhtmltopdf 实现批量对网页转为图片的好工具,快速实现大量卡片制作

欢迎来到涛涛聊AI 1、需求痛点 在学习当中经常遇到一些知识点&#xff0c;想和大家分享。但只有文本形式&#xff0c;很多人不愿意去阅读&#xff0c;也看不到重点。 如果自己去单独设计页面版式&#xff0c;又太浪费时间。那就想着有没有一种方法&#xff0c;可以把一个知识…...

case客户续保预测中用到的特征工程、回归分析和决策树分析的总结

文章目录 [toc]1. 回归分析概述1.1 基本概念1.2 与分类的区别 2. 常见回归算法2.1 线性回归2.2 决策树回归2.3 逻辑回归&#xff08;Logistic Regression&#xff09;2.3 其他算法补充&#xff1a;通俗版&#xff1a;决策树 vs 随机森林&#x1f333; 决策树&#xff1a;像玩「…...

最新如何在服务器中解决FFmpeg下载、安装和配置问题教程(Linux|Windows|Mac|Ubuntu)

最新如何在服务器中解决FFmpeg下载、安装和配置问题教程&#xff08;Linux&#xff5c;Windows&#xff5c;Mac&#xff5c;Ubuntu&#xff09; 摘要&#xff1a; FFmpeg是一个强大的开源工具&#xff0c;广泛应用于音视频处理&#xff0c;支持格式转换、视频剪辑、流媒体推送…...

vue webSocket

vue webSocket 一、vue2 webSocketwebSocket.jsvue2 二、vue3 webSocket tswebSocket.tsvue3 一、vue2 webSocket webSocket.js export default {data() {return {websock: null, // 建立的连接&#xff0c;存websocket实例化的lockReconnect: false, // 是否真正建立连接…...

Flask+Influxdb+grafna构建电脑性能实时监控系统

Influx下载地址&#xff0c;这里下载了以下版本influxdb-1.8.5_windows_amd64.zip 运行前需要先启动Influx数据库&#xff1a; 管理员方式运行cmd->F:->cd F:\influxdb\influxdb-1.8.5-1->influxd -config influxdb.conf&#xff0c;以influxdb.conf配置文件启动数…...

【golang/jsonrpc】go-ethereum中json rpc初步使用(websocket版本)

说在前面 操作系统&#xff1a;win11 wsl2go-ethereum版本&#xff1a;1.15.8 关于json-rpc 官网 server 定义方法type CalculatorService struct{}func (s *CalculatorService) Add(a, b int) int {return a b }func (s *CalculatorService) Div(a, b int) (int, error) {…...

【C++】 —— 笔试刷题day_15

刷题day_15&#xff0c;继续加油&#xff01;&#xff01;&#xff01; 一、平方数 题目解析 题目给出一个数&#xff0c;让我们找到离它最近的一个平方数&#xff0c;然后输出即可。 算法思路 这道题总体来说还是非常简单的。 这里先来看一种思路&#xff0c;就是从1开始找…...

网站备案详解

当小型网站开发完毕具备上线条件后&#xff0c;需要完成域名映射与相关备案&#xff0c;才能合法运维。就像婴儿出生后&#xff0c;要开出生证明并去派出所上户口一样&#xff0c;备案后就是有“户口”的网站啦。具体效果见&#xff1a;CodingLife 一&#xff1a;服务器部署 …...

IPV6应用最后的钥匙:DDNS-GO 动态域名解析工具上手指南--家庭云计算专家

DDNS-GO作为一款轻量级开源工具&#xff0c;其IPv6功能通过自动化动态域名解析&#xff0c;有效解决了家庭网络因运营商动态分配IPv6地址导致的访问难题。用户无需复杂配置&#xff0c;即可将冗长的IPv6地址绑定至易记域名&#xff0c;并实时同步IP变化&#xff0c;显著提升了N…...

ubuntu 系统安装Mysql

安装 mysql sudo apt update sudo apt install mysql-server 启动服务 sudo systemctl start mysql 设置为开机自启 sudo systemctl enable mysql 查看服务状态 &#xff08;看到类似“active (running)”的状态信息代表成功&#xff09; sudo systemctl status mysql …...

Go:方法

方法声明 type point struct { X, Y float64 }// 普通函数 func Distance(p, q Point) float64 {return math.Hypot(q.x - p.x, q.y - p.Y) }// Point类型的方法 func (p Point) Distance(q Point) float64 {return math.Hypot(q.x - p.x, q.y - p.Y) }方法声明与普通函数声…...

十四种逻辑器件综合对比——《器件手册--逻辑器件》

目录 逻辑器件 简述 按功能分类 按工艺分类 按电平分类 特殊功能逻辑器件 应用领域 详尽阐述 1 逻辑门 一、基本概念 二、主要类型 三、实现方式 四、应用领域 2 反相器 工作原理 基本功能 主要应用 常见类型 特点 未来发展趋势 3 锁存器 基本概念 工作原理 主要类型…...

[网鼎杯 2022 青龙组]fakeshell

这个题&#xff0c;我们查壳之后是upx壳。 但是当我们用upxunpack解包的时候我们解不出来。 说明有人动过这个包。 然后我们打开010eider&#xff0c;修改他的魔改 将此处&#xff0c;我们改成UPX我们在解包就可以了。然后我重新使用upxunpack 之后我们成功得到未加密的文件…...

vivado + modelsim 仿真:Post-Synthesis Timing Simulation

Vivado 结合Modelsim 实现综合后仿真的一种方法 Post-Synthesis Timing Simulation 使用Vivado 生成仿真所需文件创建Modelsim工程参考文档 使用Vivado 生成仿真所需文件 Vivado simulation 中可勾选Generate simulation scripts only;勾选-sdf_anno; 在testbanch文件中例化gl…...

可能存在特殊情况,比如控制台显示有延迟、缓冲问题等影响了显示顺序。

从控制台输出看&#xff0c;正常逻辑应是先执行 System.out.println(" 未处理异常演示 "); 输出对应文本&#xff0c;再因 arr 为 null 访问 length 触发 NullPointerException 输出异常信息。可能存在特殊情况&#xff0c;比如控制台显示有延迟、缓冲问题等影响…...

使用Python建模量子隧穿

引言 量子隧穿是量子力学中的一个非常有趣且令人神往的现象。在经典物理学中,我们通常认为粒子必须克服一个势垒才能通过它。但是,在量子力学中,粒子有时可以“穿越”一个势垒,即使它的能量不足以克服这个势垒。这种现象被称为“量子隧穿”。今天,我们将通过 Python 来建…...