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

二叉树进阶学习——从前序和中序遍历序列构造二叉树

1.题目解析

题目来源:105.从前序与中序遍历序列构造二叉树——力扣

测试用例

2.算法原理

首先要了解一个概念

前序遍历:按照 根节点->左子树->右子树的顺序遍历二叉树

中序遍历:按照 左子树->根节点->右子树的顺序遍历二叉树

题目中我们可知需要根据给出的前序遍历序列与中序遍历序列构建一个二叉树,解题思路就是通过前序序列确定根节点,然后根据找出的根节点将中序序列分为:[左子树,根节点,右子树]这样三个范围,然后递归构造左子树与右子树,以此类推直到完成构建

3.实战代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* build(vector<int>& preorder, vector<int>& inorder,int& previ,int inbegin,int inend){if(inbegin > inend){return nullptr;}//创建根节点TreeNode* root = new TreeNode(preorder[previ]);//通过前序确定根节点后将中序数组分为三部分//左子树 根节点 右子树int rooti = inbegin;while(inbegin <= inbegin){if(inorder[rooti] == preorder[previ]){break;}//寻找中序中的根节点所在的的位置rooti++;}//此时前序中的根节点构建完成,向后构建其他子树的根节点previ++;//左子树递归构建[inbegin,rooti-1]区间//右子树递归构建[root+1,inend]区间root->left = build(preorder,inorder,previ,inbegin,rooti-1);root->right = build(preorder,inorder,previ,rooti+1,inend);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i = 0;return build(preorder,inorder,i,0,preorder.size()-1);}
};

相关文章:

二叉树进阶学习——从前序和中序遍历序列构造二叉树

1.题目解析 题目来源&#xff1a;105.从前序与中序遍历序列构造二叉树——力扣 测试用例 2.算法原理 首先要了解一个概念 前序遍历&#xff1a;按照 根节点->左子树->右子树的顺序遍历二叉树 中序遍历&#xff1a;按照 左子树->根节点->右子树的顺序遍历二叉树 题目…...

【数据分享】2000—2023年我国省市县三级逐年植被覆盖度(FVC)数据(Shp/Excel格式)

之前我们分享过2000—2023年逐月植被覆盖度&#xff08;FVC&#xff09;栅格数据&#xff08;可查看之前的文章获悉详情&#xff09;和Excel和Shp格式的省市县三级逐月FVC数据&#xff08;可查看之前的文章获悉详情&#xff09;&#xff0c;原始的逐月栅格数据来源于高吉喜学者…...

【Python】Streamlit:为数据科学与机器学习打造的简易应用框架

Streamlit 是一个开源的 Python 库&#xff0c;专为数据科学家和机器学习开发者设计&#xff0c;旨在快速构建数据应用。通过简单的 Python 脚本&#xff0c;开发者无需掌握前端技术&#xff0c;即可将数据分析和模型结果转化为直观、交互式的 Web 应用。其简洁的 API 设计使得…...

OpenJudge | 置换选择排序

总时间限制: 1000ms 内存限制: 65536kB 描述 给定初始整数顺串&#xff0c;以及大小固定并且初始元素已知的二叉最小堆&#xff08;为完全二叉树或类似完全二叉树&#xff0c;且父元素键值总小于等于任何一个子结点的键值&#xff09;&#xff0c;要求利用堆实现置换选择排序&a…...

如何提取b站的视频字幕,下载视频

打开视频地址 按F12打开—开发者工具 在开发者工具打开Network 过滤器关键字&#xff1a; 自动生成字幕&#xff1a;ai_subtitle 自制&#xff1a;json 打开/关闭字幕 刷新页面 找到字幕 点选字幕的respond 将方框中的内容复制&#xff1b; 复制到&#xff1a;https://www.drea…...

Vue中使用ECharts实现热力图的详细教程

在数据可视化领域&#xff0c;热力图是一种非常直观的表现形式&#xff0c;它通过颜色深浅来展示数据分布情况。在Vue项目中&#xff0c;我们可以使用ECharts这一强大的图表库来实现热力图。下面我将详细介绍如何在Vue中使用ECharts实现热力图。效果如下图&#xff1a; 一、准备…...

Arduino UNO R3自学笔记13 之 Arduino使用LM35如何测量温度?

注意&#xff1a;学习和写作过程中&#xff0c;部分资料搜集于互联网&#xff0c;如有侵权请联系删除。 前言&#xff1a;学习使用传感器测温。 1.LM35介绍 一般来讲当知道需求&#xff0c;就可以 通过既定要求的条件来筛选需要的器件&#xff0c;多方面的因素最终选定了器件…...

蓝桥杯【物联网】零基础到国奖之路:十六. 扩展模块之矩阵按键

蓝桥杯【物联网】零基础到国奖之路:十六. 扩展模块之矩阵按键 第一节 硬件解读第二节 CubeMX配置第三节 MDK代码 第一节 硬件解读 扩展模块和ADC模块是一摸一样的&#xff0c;插在主板上。 引脚对应关系&#xff1a; PB6-ROW1 PB7-ROW2 PB1-COLUMN1 PB0-COLUMN2 PA8-COLUMN3 …...

Apollo9.0 Planning2.0决策规划算法代码详细解析 (4): PlanningComponent::Proc()

&#x1f31f; 面向自动驾驶规划算法工程师的专属指南 &#x1f31f; 欢迎来到《Apollo9.0 Planning2.0决策规划算法代码详细解析》专栏&#xff01;本专栏专为自动驾驶规划算法工程师量身打造&#xff0c;旨在通过深入剖析Apollo9.0开源自动驾驶软件栈中的Planning2.0模块&am…...

AAA Redis的过期删除策略+缓存雪崩+缓存一致性问题

目录 一、三种删除策略比较 二、缓存雪崩缓存击穿缓存穿透 三、缓存一致性 Redis学习笔记 一、三种删除策略比较 内存占用CPU占用特征定时删除节约内存&#xff0c;无占用不分时段占用CPU资源&#xff0c;频度高时间换空间惰性删除内存占用严重延时执行&#xff0c;CPU利用…...

成都跃享未来教育咨询有限公司抖音小店:引领教育咨询新风尚

在数字化浪潮席卷全球的今天&#xff0c;教育咨询行业正经历着前所未有的变革。成都跃享未来教育咨询有限公司&#xff0c;作为教育行业的一颗璀璨新星&#xff0c;凭借其前瞻性的教育理念与创新的运营模式&#xff0c;在抖音平台上开设了小店&#xff0c;不仅为广大学子及家长…...

【堆排】为何使用向下调整法建堆比向上调整法建堆更好呢?

文章目录 前言一、堆排代码一、计算使用向上调整法建堆的时间复杂度二、计算使用向下调整法插入的时间复杂度总结 前言 在博主的上一篇博客堆排(链接在这里点击即可)的总结中提出啦使用向下调整法建堆比使用向上调整法建堆更好&#xff0c;是因为使用向上调整法建堆的时间复杂…...

在Stable Diffusion WebUI中安装SadTalker插件时几种错误提示的处理方法

SD中的插件一般安装比较简单&#xff0c;但也有一些插件安装会比较难。比如我在安装SadTalker时&#xff0c;就遇到很多问题&#xff0c;一度放弃了&#xff0c;后来查了一些网上攻略&#xff0c;自己也反复查看日志&#xff0c;终于解决&#xff0c;不吐不快。 一、在Stable …...

使用ffmpeg合并视频和音频

使用ffmpeg合并视频和音频 - 哔哩哔哩 简介 FFmpeg是一套可以用来记录、转换数字音频、视频&#xff0c;并能将其转化为流的开源计算机程序。采用LGPL或GPL许可证。它提供了录制、转换以及流化音视频的完整解决方案。它包含了非常先进的音频/视频编解码库libavcodec&#xff0…...

周末总结(2024/10/05)

工作 人际关系核心实践&#xff1a; 要学会随时回应别人的善意&#xff0c;执行时间控制在5分钟以内 坚持每天早会打招呼 遇到接不住的话题时拉低自己&#xff0c;抬高别人(无阴阳气息) 朋友圈点赞控制在5min以内&#xff0c;职场社交不要放在5min以外 职场的人际关系在面对利…...

在Ubuntu中自动挂载SMB/CIFS共享

文章目录 0. 引言1. 使用credentials文件存储认证信息2. 挂载点的准备3. 必要软件的安装4. 调整挂载参数5. 测试挂载6. 日志调试 0. 引言 本文是自己挂载共享磁盘的实践记录&#xff0c;将详细介绍如何在Linux系统中配置自动挂载SMB/CIFS共享&#xff0c;并提供一些常见问题的…...

pWnOS2.0 靶机渗透( cms 渗透,php+mysql 网站渗透,密码碰撞)

pWnOS2.0 靶机渗透( ) 靶机介绍 vulnhub 靶机 本地搭建 由于靶机特性&#xff0c;靶机网卡位nat模式扫不到&#xff0c;原来需要改 nat 的地址 参考方法 https://blog.csdn.net/Bossfrank/article/details/131415257 作者主页 https://blog.csdn.net/Bossfrank?typeblog P…...

【AI】AIOT简介

随着技术的快速发展&#xff0c;人工智能AI和物联网IoT已经成为当今最热门的技术领域。AIOT是人工智能和物联网的结合&#xff0c;使物联网设备更加智能化&#xff0c;能够进行自主决策和学习的技术。 通过物联网产生、收集来自不同维度的、海量的数据存储于云端、边缘端&#…...

picgo + typora + gitee图床

Picgo打造个人图床&#xff0c;稳定又安全 解决Typora笔记上传到CSDN图片无法显示的问题 typora中...

【路径规划】多机器人路径规划

摘要 多机器人路径规划在现代自动化、仓储管理及智能交通系统中有着广泛的应用。本文提出了一种基于A*算法的多机器人路径规划方法&#xff0c;旨在解决多机器人在同一环境中的路径冲突问题。通过采用启发式搜索和路径优化策略&#xff0c;机器人能够在保持避障的前提下实现最…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...