LeetCode105. 从前序与中序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树
文章目录
- [105. 从前序与中序遍历序列构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)
- 一、题目
- 二、题解
一、题目
给定两个整数数组 preorder
和 inorder
,其中 preorder
是二叉树的先序遍历, inorder
是同一棵树的中序遍历,请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
提示:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder
和inorder
均 无重复 元素inorder
均出现在preorder
preorder
保证 为二叉树的前序遍历序列inorder
保证 为二叉树的中序遍历序列
二、题解
算法思路:
我们要根据给定的前序遍历和中序遍历序列构建出一棵二叉树。前序遍历序列告诉我们根节点的值以及左子树和右子树的分割点,中序遍历序列告诉我们左子树和右子树的节点排列顺序。我们可以通过递归的方法来实现构建二叉树的过程。
具体步骤如下:
- 从前序遍历序列中取出第一个元素,它是当前子树的根节点的值。
- 在中序遍历序列中找到该根节点的值,根据这个值,将中序序列划分为左子树部分和右子树部分。
- 根据左子树和右子树的节点数量,在前序遍历序列中划分出左子树的前序序列和右子树的前序序列。
- 递归地构建左子树和右子树。
具体实现:
class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {// 基准情况:如果前序遍历序列为空,返回空指针表示空树if (preorder.size() == 0) {return nullptr;}// 创建当前子树的根节点TreeNode *root = new TreeNode();root->val = preorder[0];// 在中序遍历序列中找到根节点的位置int index = 0;for (index = 0; index < inorder.size(); index++) {if (inorder[index] == preorder[0]) {break;}}// 划分左子树和右子树的序列vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + index + 1);vector<int> leftInorder(inorder.begin(), inorder.begin() + index);vector<int> rightPreorder(preorder.begin() + index + 1, preorder.end());vector<int> rightInorder(inorder.begin() + index + 1, inorder.end());// 递归构建左子树和右子树root->left = buildTree(leftPreorder, leftInorder);root->right = buildTree(rightPreorder, rightInorder);return root;}
};
算法分析:
-
时间复杂度:在每次递归中,我们都需要遍历中序遍历序列来找到根节点的位置,这需要 O(n) 的时间,其中 n 是节点数量。递归的总时间复杂度取决于递归的层数以及每层的操作,因此总体时间复杂度为 O(n)。
-
空间复杂度:每次递归都会创建新的前序和中序序列,空间复杂度主要取决于递归的深度,最坏情况下递归深度为 n,所以空间复杂度为 O(n)。此外,还需要存储二叉树节点的空间,所以总体空间复杂度也为 O(n)。
相关文章:

LeetCode105. 从前序与中序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树 文章目录 [105. 从前序与中序遍历序列构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)一、题目二、题解 一、题目 给定两个整数数组 preorder 和 inorder ,其中 preo…...

编码技巧——Sentinel的blockHandler与fallback
本文介绍Sentinel的blockHandler与fallback的区别,背景是:发生限流时,配置的sentinel的blockhandler没有生效而fallback生效了;排查原因,从而给出Sentinel配置异常降级和限流降级的代码写法; 在查看源码前…...

最新成果展示:GaN基Micro-LED热学模型数据库的开发及应用
由于GaN基Micro-LED表面积-体积比增加,其在热学方面的性质有别于大尺寸的LED,如缺陷复合导致的热效应将在发光区域中产生诸多“热”点,导致发光波长不均匀,这将影响后期显示系统的成像稳定性。针对上述问题,天津赛米卡…...

【Vue3】动态组件
动态组件的基本使用 动态组件(Dynamic Components)是一种在 Vue 中根据条件或用户输入来动态渲染不同组件的技术。 在 Vue 中使用动态组件,可以使用 元素,并通过 is 特性绑定一个组件的名称或组件对象。通过在父组件中改变 is 特…...
Java超级玛丽小游戏制作过程讲解 第五天 创建并完成常量类04
//加载障碍物 try {obstacle.add(ImageIO.read(new File(path"brick.png")));obstacle.add(ImageIO.read(new File(path"soil_up.png")));obstacle.add(ImageIO.read(new File(path"soil_base.png"))); } catch (IOException e) {e.printStackTr…...
设置浏览器兼容
浏览器兼容 css兼容 cursor定义手型 Firefox不支持hand,IE支持pointer 解决方法:统一使用pointercss透明 IE:filter:progid:DXImageTransform.Microsoft.Alpha(style0,opacity60) Firefox:opacity:0.6 解决…...
Java # List
ArrayList<>() import java.util.ArrayList; // 引入 ArrayList 类ArrayList<E> objectName new ArrayList<>(); // 初始化 常用方法 方法描述add()将元素插入到指定位置的 arraylist 中addAll()添加集合中的所有元素到 arraylist 中clear()删除 arrayl…...

git原理与使用
目录 引入基本操作分支管理远程操作标签管理 引入 假设你的老板要你设计一个文档,当你设计好了,拿给他看时,他并不是很满意,就要你拿回去修改,你修改完后,再给他看时,他还是不满意,…...

【C语言题解】将一句话的单词进行倒置,标点不倒置。
题目描述:将一句话的单词进行倒置,标点不倒置。比如 “I like beijing.”,经过处理后变为:“beijing. like I”。 文章目录 原题目题目描述:输入描述:输出描述:题目链接: 整体思路分…...

Postman 的简单使用
什么是Postman 在程序开发中用于调试网络程序或者跟踪网页请求。可以对网页进行简单的基本信息调试。Postman最早是作用chrome浏览器插件存在的,但是2018年初Chrome停止对Chrome应用程序的支持。所以现在Postman提供了独立的安装包,不再依赖于Chrome浏览…...
在CentOS7安装部署GitLab服务
CentOS 7 安装 Gitlab 官方安装教程:https://about.gitlab.com/install/ 参考安装教程:https://developer.aliyun.com/article/74395 安装配置 Step1:配置yum源 vim /etc/yum.repos.d/gitlab-ce.repo存入以下内容: [gitlab-c…...

订单系统就该这么设计,稳的一批~
订单功能作为电商系统的核心功能,由于它同时涉及到前台商城和后台管理系统,它的设计可谓是非常重要的。就算不是电商系统中,只要是涉及到需要交易的项目,订单功能都具有很好的参考价值,说它是通用业务功能也不为过。今…...

Agents改变游戏规则,亚马逊云科技生成式AI让基础模型加速工作流
最近,Stability AI正式发布了下一代文生图模型——Stable Diffusion XL 1.0这次的1.0版本是Stability AI的旗舰版生图模型,也是最先进的开源生图模型。 在目前的开放式图像模型中,SDXL 1.0是参数数量最多的。官方表示,这次采用的…...

详细教程:如何搭建废品回收小程序
废品回收是一项环保举措,通过回收和再利用废弃物品,可以减少资源浪费和环境污染。近年来,随着智能手机的普及,小程序成为了推广和运营的重要工具。本文将详细介绍如何搭建一个废品回收小程序。 1. 进入乔拓云网后台 首先…...
什么是双亲委派机制?
什么是双亲委派机制? Parent Delegation Model ,直译过来可能叫做父级委托模型更容易理解 类的加载过程 Java 编译器将 Java源文件编译成.class 文件再由 JVM 加载 .class 文件到内存中JVM 装载完成后得到一个 Class 字节码对象拿到字节码对象之后 &a…...

Mageia 9 RC1 正式发布,Mandriva Linux 发行版的社区分支
导读Mageia 9 首个 RC 已发布。公告写道,自 2023 年 5 月发布 beta 2 以来,Mageia 团队一直致力于解决许多顽固问题并提供安全修复和新特性。 新版本的控制中心添加了用于删除旧内核的新功能,该功能在 Mageia 9 中默认自动启用,用…...

ChatGPT: 人机交互的未来
ChatGPT: 人机交互的未来 ChatGPT背景ChatGPT的特点ChatGPT的应用场景结论 ChatGPT ChatGPT是一种基于大数据和机器学习的人工智能聊天机器人模型。它由国内团队发明、开发,并被命名为Mental AI。ChatGPT的目标是通过模拟自然对话的方式,提供高效、智能…...

Linux 常用操作命令
Linux简介及Ubuntu安装 Linux,免费开源,多用户多任务系统。基于Linux有多个版本的衍生。RedHat、Ubuntu、Debian 安装VMware或VirtualBox虚拟机。具体安装步骤,找百度。 再安装Ubuntu。具体安装步骤,找百度。 常用指令 ls …...

24届近5年重庆邮电大学自动化考研院校分析
今天给大家带来的是重庆邮电大学控制考研分析 满满干货~还不快快点赞收藏 一、重庆邮电大学 学校简介 重庆邮电大学简称"重邮",坐落于直辖市-重庆市,入选国家"中西部高校基础能力建设工程”、国家“卓越工程师教育培养计划…...
如何对oracle和mysql进行 分区分表
前提:使用自带的分区和分表机制进行操作 oracle,mysql分区分表 分区 分区是一种将一个大的表或索引分割成多个小的部分的技术,每个部分称为一个分区。分区可以提高数据的管理和查询效率,因为可以根据不同的条件对不同的分区进行操作&#x…...

XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...

uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
MySQL JOIN 表过多的优化思路
当 MySQL 查询涉及大量表 JOIN 时,性能会显著下降。以下是优化思路和简易实现方法: 一、核心优化思路 减少 JOIN 数量 数据冗余:添加必要的冗余字段(如订单表直接存储用户名)合并表:将频繁关联的小表合并成…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...