当前位置: 首页 > 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…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...