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

AcWing 1256:扩展二叉树

【题目来源】
https://www.acwing.com/problem/content/1258/

【题目描述】
由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树,所以对二叉树做如下处理,将二叉树的空结点用
· 补齐,如图所示。
我们把这样处理后的二叉树称为原二叉树的
扩展二叉树,扩展二叉树的先序后序序列均能唯一确定其二叉树。

现给出扩展二叉树的先序序列,要求输出原二叉树中序和后序序列。

【输入格式】
扩展二叉树的先序序列。

【输出格式】
输出其中序和后序序列。

【数据范围】
原二叉树的结点数不超过 
26,且均由大写字母表示。

【输入样例】
ABD..EF..G..C..

【输出样例】
DBFEGAC
DFGEBCA

【算法分析】
扩展二叉树的前序遍历相当于普通二叉树的“前序+中序”,能唯一确定二叉树的形状;
扩展二叉树的后序遍历相当于普通二叉树的“后续+中序”,能唯一确定二叉树的形状。

【算法代码】

#include <bits/stdc++.h>
using namespace std;string pre;
string in,post;
int k;void dfs() {char root=pre[k++];if(root=='.') return;dfs(); //Enter the left subtreein+=root;dfs(); //Enter the right subtreepost+=root;
}int main() {cin>>pre;dfs();cout<<in<<endl;cout<<post<<endl;return 0;
}/*
in:
ABD..EF..G..C..out:
DBFEGAC
DFGEBCA
*/




【参考文献】
https://www.cnblogs.com/0fflineboy/p/15403913.html
https://www.acwing.com/solution/content/36138/

https://blog.csdn.net/m0_72895175/article/details/132356141




 

相关文章:

AcWing 1256:扩展二叉树

【题目来源】https://www.acwing.com/problem/content/1258/【题目描述】 由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树&#xff0c;所以对二叉树做如下处理&#xff0c;将二叉树的空结点用 补齐&#xff0c;如图所示。 我们把这样处理后的二叉树称为原二叉树…...

三维家:SaaS的IT规模化降本之道|OceanBase 《DB大咖说》(十一)

OceanBase《DB大咖说》第 11 期&#xff0c;我们邀请到了三维家的技术总监庄建超&#xff0c;来分享他对数据库技术的理解&#xff0c;以及典型 SaaS 场景在数据库如何实现规模化降本的经验与体会。 庄建超&#xff0c;身为三维家的技术总监&#xff0c;独挑大梁&#xff0c;负…...

ai智能语音机器人是如何影响客户体验的?电销机器人部署

随着人工智能技术的进步&#xff0c;越来越多的企业在寻求如何将人工智能技术融合到现有的商业模式上&#xff0c;进而实现自动化、智能化。在通信行业大量使用智能语音机器人、聊天机器人、客服机器人时&#xff0c;它能和“客户体验”并驾齐驱吗&#xff0c;还是可以让客户体…...

vue3使用v-html实现文本关键词变色

首先看应用场景 这有一段文本内容&#xff0c;是项目的简介&#xff0c;想要实现将文本中的关键词进行变色处理 有如下关键词 实现思路 遍历文本内容&#xff0c;找到关键词&#xff0c;并使用某种方法更改其字体样式。经过搜寻资料决定采用v-html实现&#xff0c;但是v-h…...

C#面:举列 a=10,b=15,在不用第三方变量的前提下,把a,b的值互换

要在不使用第三方变量的前提下交换a和b的值&#xff0c;可以使用异或运算。异或运算的特性是&#xff0c;对于两个相同的数进行异或运算&#xff0c;结果为0&#xff1b;对于任意数与0进行异或运算&#xff0c;结果为该数本身。因此&#xff0c;可以通过多次异或运算来实现变量…...

编写动态库

1.创建库.c .h文件 2.编写Makefile文件 3.make之后形成.so文件 4.make output,形成mylib 5.把mylib拷贝到test里面 mv mylib /test 6.编译 gcc main.c -I mylib/include -L mylib/lib -lmymethod形成a.out 但是直接执行会出现以下问题 很显然没有找到动态库 7.解决加载找不…...

记一次阿里云服务器java应用无法响应且无法远程连接的问题排查

问题表现 java服务无响应&#xff0c;无法远程链接到服务器。 今天中午12点多&#xff0c;应用直接崩溃。后续进入到服务器&#xff0c;发现java进程都不在了&#xff0c; 排查过程 先安装atop工具 安装、配置并使用atop监控工具 等下次再出现时看相关时间点日志&#xff…...

雷池WAF+Modsecurity安装防护及系统加固

君衍. 一、雷池WAF1、什么是雷池2、什么是WAF3、雷池的功能4、WAF部署架构5、整体检测流程 二、雷池WAF环境依赖1、查看本地CPU架构2、Docker安装2.1 卸载旧版本2.2 安装yum-utils工具包2.3 设置镜像仓库2.4 安装docker2.5 启动docker并查看版本 3、Docker Compose安装3.1 卸载…...

【Python】已解决:SyntaxError: positional argument follows keyword argument

文章目录 一、分析问题背景二、可能出错的原因三、错误代码示例四、正确代码示例五、注意事项 已解决&#xff1a;SyntaxError: positional argument follows keyword argument 一、分析问题背景 在Python编程中&#xff0c;当我们在调用函数时混合使用位置参数&#xff08;p…...

leetcode-20-回溯-切割、子集

一、[131]分割回文串 给定一个字符串 s&#xff0c;将 s 分割成一些子串&#xff0c;使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ] 分析&…...

利用深度学习模型进行语音障碍自动评估

语音的产生涉及器官的复杂协调&#xff0c;因此&#xff0c;语音包含了有关身体各个方面的信息&#xff0c;从认知状态和心理状态到呼吸条件。近十年来&#xff0c;研究者致力于发现和利用语音生物标志物——即与特定疾病相关的语音特征&#xff0c;用于诊断。随着人工智能&…...

TP8 JS(html2canvas) 把DIV内容生成二维码并与背景图、文字组合生成分享海报

方法一&#xff1a;前端JS生成(推荐) 注意&#xff1a; 1.这个网页只能截图图片效果代码&#xff0c;其它任何html效果都不能有&#xff0c;不然截图就不准确 2.如果要生成的图片DIV内容中引用了第三个方的图片&#xff0c;就是不使用同一个域名下的图片&#xff0c;需要把后…...

计算机科学中的接口(Interface)介绍

计算机科学中的接口&#xff08;Interface&#xff09;介绍 计算机科学中&#xff0c;接口是一个广泛的概念&#xff0c;在不同上下文中有不同含义&#xff1a; 1.任何两电路或设备间的连接电路&#xff0c;用于连接CPU与内存、CPU与外设之间。这是一个重要的硬件层面的接口概…...

大创项目推荐 题目:基于深度学习卷积神经网络的花卉识别 - 深度学习 机器视觉

文章目录 0 前言1 项目背景2 花卉识别的基本原理3 算法实现3.1 预处理3.2 特征提取和选择3.3 分类器设计和决策3.4 卷积神经网络基本原理 4 算法实现4.1 花卉图像数据4.2 模块组成 5 项目执行结果6 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 基…...

黑芝麻科技A1000简介

文章目录 1. A1000 简介2. 感知能力评估3. 竞品对比4. 系统软件1. A1000 简介...

详解C语言分支与循环语句

分支语句 if elseswitch 循环语句 whilefordo while goto语句 文章目录 1.什么是语句2.分支语句&#xff08;选择结构&#xff09;2.1 if语句2.1.1 悬空else2.1.3 练习 2.2 switch语句2.2.1 在switch语句中的break2.2.2 default子句 3.循环语句3.1 while循环3.1.1 while语句中…...

Python商务数据分析知识专栏(五)——Python数据分析的应用③使用Pandas进行数据预处理

Python商务数据分析知识专栏&#xff08;五&#xff09;——Python数据分析的应用③使用Pandas进行数据预处理 使用Pandas进行数据预处理1.合并数据2.清洗数据3.标准化数据4.转换数据 使用Pandas进行数据预处理 1.合并数据 2.清洗数据 3.标准化数据 4.转换数据...

Nosql期末复习

mongodb基本常用命令&#xff08;只要掌握所有实验内容就没问题&#xff09; 上机必考&#xff0c;笔试试卷可能考&#xff1a; 1.1 数据库的操作 1.1.1 选择和创建数据库 &#xff08;1&#xff09;use dbname 如果数据库不存在则自动创建&#xff0c;例如&#xff0c;以下…...

Pytest+Allure+Yaml+PyMsql+Jenkins+Gitlab接口自动化(四)Jenkins配置

一、背景 Jenkins&#xff08;本地宿主机搭建&#xff09; 拉取GitLab(服务器)代码到在Jenkins工作空间本地运行并生成Allure测试报告 二、框架改动点 框架主运行程序需要先注释掉运行代码&#xff08;可不改&#xff0c;如果运行报allure找不到就直接注释掉&#xff09; …...

SQL面试题练习 —— 查询前2大和前2小用户并有序拼接

目录 1 题目2 建表语句3 题解 1 题目 有用户账户表&#xff0c;包含年份&#xff0c;用户id和值,请按照年份分组&#xff0c;取出值前两小和前两大对应的用户id&#xff0c;需要保持值最小和最大的用户id排首位。 样例数据 ------------------------- | year | user_id | v…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...