先序+中序还原二叉树【数据结构】
先序+中序还原二叉树
题目描述
给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度。
输入
输入首先给出正整数N(≤50),为树中结点总数。下面两行先后给出先序和中序遍历序列,均是长度为N的不包含重复英文字母(区别大小写)的字符串。
输出
输出为一个整数,即该二叉树的高度。
输入样例1
9
ABDFGHIEC
FDHGIBEAC
输出样例1
5
#include<bits/stdc++.h>
using namespace std;
int high=0;
struct trees
{char value;trees* left=NULL;trees* right=NULL;
};
trees* setTree(int pl,int pr,int ml,int mr,map<char,int> &m,string prior,string middle,int height)
{//根节点char root=prior[pl];//根节点在中序遍历序列的位置int middleIndex=m[root];trees* tree = new trees;tree->value=root;if(middleIndex>ml) tree->left=setTree(pl+1,pl+middleIndex-ml,ml,middleIndex-1,m,prior,middle,height+1);if(middleIndex<mr) tree->right=setTree(pl+middleIndex-ml+1,pr,middleIndex+1,mr,m,prior,middle,height+1);high=max(high,height);return tree;
}
int main()
{int n;cin>>n;//记录字符在中序遍历序列位置map<char,int> m;string prior,middle;cin>>prior>>middle;for(int i=0;i<middle.size();i++) m[middle[i]]=i;trees* t=new trees;//建树t=setTree(0,n-1,0,n-1,m,prior,middle,1);cout<<high<<endl;return 0;
}
相关文章:
先序+中序还原二叉树【数据结构】
先序中序还原二叉树 题目描述 给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度。 输入 输入首先给出正整数N(≤50),为树中结点总数。下面两行先后给出先序和中序遍历序列,均是长度为N的不包含重…...
【全网首发】洛谷P2678 [NOIP2015 提高组] 跳石头
Everyday English You don’t become what you want; you become whatyou believe. —Oprah Winfrey 你不是成为你想要的,你成为你所相信的。 洛谷P2678 [NOIP2015 提高组] 跳石头 题目描述 一年一度的“跳石头”比赛又要开始了! 这项比赛将在一条笔…...
Gpt指引ubuntu安装java8/11
在Ubuntu系统上安装Java环境通常包括以下几个步骤: 更新软件包索引: 在安装新软件之前,最好先更新Ubuntu的软件包索引。这可以确保你安装的是最新版本的软件包。可以使用以下命令来更新: sudo apt update安装Java: U…...
【MCAL】TC397+EB-tresos之MCU配置实战 - 芯片时钟
本篇文章介绍了在TC397平台使用EB-treso对MCU驱动模块进行配置的实战过程,主要介绍了后续基本每个外设模块都要涉及的芯片时钟部分,帮助读者了解TC397芯片的时钟树结构,在后续计算配置不同外设模块诸如通信速率,定时器周期等&…...
最新AI系统ChatGPT网站H5系统源码,支持AI绘画,GPT语音对话+ChatFile文档对话总结+DALL-E3文生图
一、前言 SparkAi创作系统是基于ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统,支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美,可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软件系统。那么如何搭建部署AI创作Ch…...
如何在MAC OS中的XCODE下添加 <bits/stdc++.h>
mac上使用的编译器是Clang,但是没有万能头文件bits/stdc.h\,本文介绍如何添加万能头文件 Xcode 版本:15.1 - 打开应用程序-Xcode-右键显示包内容 Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/includ…...
Maven项目提示Ignored pom.xml问题
1 环境 (1)IDEA开发工具:2022.2.1 (2)JDK:Java17(Spring6要求JDK最低版本是Java17) (3)Spring:6.1.2 (4)Maven 3.8.8 2 …...
SQL学习汇总
数据库将两张没有关联的表进行横向连接数据库将两张表进行横向连接(拼接成一张表的形式显示)_db2 两条记录如果相同就横向显示-CSDN博客 mysql统计某个字段的比例_mysql查询一行某个字段占整个字段sum的比例-CSDN博客 Spark 系列(十二&…...
单片机MCU堆栈概念与区别
C语言中的堆栈是用于存储函数调用、局部变量以及程序执行期间所需的临时数据的内存区域。堆栈由编译器自动管理,是一种后进先出(LIFO)的数据结构。堆栈空间大小指的是分配给堆栈的内存空间大小,它限制了函数调用和局部变量的深度和…...
C#中使用is关键字检查对象是否与给定类型兼容
目录 一、定义 二、示例 三、生成 在程序的开发过程中经常会使用类型转换,如果类型转换不成功则会出现异常,从抛出异常到捕获并处理异常,无形中增加了系统的开销,而且太过频繁地处理异常还会严重地影响系统的稳定性。is关键字可…...
AI时代下,如何看待“算法利维坦”?
ChatGPT的浪潮从2022年袭来后,至今热度不减,呈现出蓬勃发展的趋势。AI家居、医疗、教育、金融、公益、农业、艺术......AI真的已经走进了生活的方方面面,我们仿佛已经进入了AI时代,势不可挡。人工智能水平如此之高,不禁…...
Linux上管理不同版本的 JDK
当在 Linux 上管理不同版本的 JDK 时,使用 yum 和 dnf 可以方便地安装和切换不同的 JDK 版本。本文将介绍如何通过这两个包管理工具安装 JDK 1.8 和 JDK 11,并利用软连接动态关联这些版本。 安装 JDK 1.8 和 JDK 11 使用 yum 安装 JDK 1.8 打开终端并…...
直方图与均衡化
直方图 统计图像中相同像素点的数量。 使用cv2.calcHist(images, channels, mask, histSize, ranges)函数 images:原图像图像格式为uint8或float32,当传入函数时应用[]括起来,例如[img]。 channels:同样用中括号括起来ÿ…...
Java——猫猫图鉴微信小程序(前后端分离版)
目录 一、开源项目 二、项目来源 三、使用框架 四、小程序功能 1、用户功能 2、管理员功能 五、使用docker快速部署 六、更新信息 审核说明 一、开源项目 猫咪信息点-ruoyi-cat: 1、一直想做点项目进行学习与练手,所以做了一个对自己来说可以完成的…...
PiflowX组件-ReadFromKafka
ReadFromKafka组件 组件说明 从kafka中读取数据。 计算引擎 flink 有界性 Unbounded 组件分组 kafka 端口 Inport:默认端口 outport:默认端口 组件属性 名称展示名称默认值允许值是否必填描述例子kafka_hostKAFKA_HOST“”无是逗号分隔的Ka…...
Ubuntu 安装MySQL以及基本使用
前言 MySQL是一个开源数据库管理系统,通常作为流行的LAMP(Linux,Apache,MySQL,PHP / Python / Perl)堆栈的一部分安装。它使用关系数据库和SQL(结构化查询语言)来管理其数据。 安装…...
基于Freeswitch实现的Volte网视频通知应用
现在运营商的Volte网络已经很好的支持视频通话了,因此在原来的电话语音通知的基础上,可以更进一步实现视频的通知,让用户有更好的体验,本文就从技术角度,基于Freeswitch来实现此类应用(本文假设读者已对Fre…...
怎么实现Servlet的自动加载
在实际开发时,有时候会希望某些Servlet程序可以在Tomcat启动时随即启动。但在默认情况下,第一次访问servlet的时候,才创建servlet对象。 如果servlet构造函数里面的代码或者init方法里面的代码比较多,就会导致用户第一次访问serv…...
15. Mysql 变量的使用
目录 变量的概述自定义变量系统变量查看系统变量系统变量赋值 局部变量总结参考资料 变量的概述 MySQL支持不同类型的变量,包括自定义变量、系统变量和局部变量。自定义变量是在会话中定义的变量,用于存储临时数据。系统变量是MySQL服务器提供的全局变量…...
为什么ChatGPT采用SSE协议而不是Websocket?
在探索ChatGPT的使用过程中,我们发现GPT采用了流式数据返回的方式。理论上,这种情况可以通过全双工通信协议实现持久化连接,或者依赖于基于EventStream的事件流。然而,ChatGPT选择了后者,也就是本文即将深入探讨的SSE&…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
手机平板能效生态设计指令EU 2023/1670标准解读
手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读,综合法规核心要求、最新修正及企业合规要点: 一、法规背景与目标 生效与强制时间 发布于2023年8月31日(OJ公报&…...
【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error
在前端开发中,JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作(如 Promise、async/await 等),开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝(r…...
tauri项目,如何在rust端读取电脑环境变量
如果想在前端通过调用来获取环境变量的值,可以通过标准的依赖: std::env::var(name).ok() 想在前端通过调用来获取,可以写一个command函数: #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...
