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

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

Python环境安装与虚拟环境配置详解

本文档旨在为Python开发者提供一站式的环境安装与虚拟环境配置指南&#xff0c;适用于Windows、macOS和Linux系统。无论你是初学者还是有经验的开发者&#xff0c;都能在此找到适合自己的环境搭建方法和常见问题的解决方案。 快速开始 一分钟快速安装与虚拟环境配置 # macOS/…...

2.2.2 ASPICE的需求分析

ASPICE的需求分析是汽车软件开发过程中至关重要的一环&#xff0c;它涉及到对需求进行详细分析、验证和确认&#xff0c;以确保软件产品能够满足客户和用户的需求。在ASPICE中&#xff0c;需求分析的关键步骤包括&#xff1a; 需求细化&#xff1a;将从需求收集阶段获得的高层需…...

Linux信号保存与处理机制详解

Linux信号的保存与处理涉及多个关键机制&#xff0c;以下是详细的总结&#xff1a; 1. 信号的保存 进程描述符&#xff08;task_struct&#xff09;&#xff1a;每个进程的PCB中包含信号相关信息。 pending信号集&#xff1a;记录已到达但未处理的信号&#xff08;未决信号&a…...

React、Git、计网、发展趋势等内容——前端面试宝典(字节、小红书和美团)

React React Hook实现架构、.Hook不能在循环嵌套语句中使用 , 为什么&#xff0c;Fiber架构&#xff0c;面试向面试官介绍&#xff0c;详细解释 用户: React Hook实现架构、.Hook不能在循环嵌套语句中使用 , 为什么&#xff0c;Fiber架构&#xff0c;面试向面试官介绍&#x…...

如何在Spring Boot中使用注解动态切换实现

还在用冗长的if-else或switch语句管理多个服务实现? 相信不少Spring Boot开发者都遇到过这样的场景:需要根据不同条件动态选择不同的服务实现。 如果告诉你可以完全摆脱条件判断,让Spring自动选择合适的实现——只需要一个注解,你是否感兴趣? 本文将详细介绍这种优雅的…...