AcWing 1260:二叉树输出
【题目来源】
https://www.acwing.com/problem/content/1262/
【题目描述】
树的凹入表示法主要用于树的屏幕或打印输出,其表示的基本思想是兄弟间等长,一个结点的长度要不小于其子结点的长度。
二叉树也可以这样表示,假设叶结点的长度为 1,一个非叶结点的长度等于它的左右子树的长度之和。
一棵二叉树的一个结点用一个字母表示(无重复),输出时从根结点开始:
每行输出若干个结点字符(相同字符的个数等于该结点长度),
如果该结点有左子树就递归输出左子树;
如果该结点有右子树就递归输出右子树。
假定一棵二叉树一个结点用一个字符描述,现在给出先序和中序遍历的字符串,用树的凹入表示法输出该二叉树。
【输入格式】
两行,每行是由大写字母组成的字符串(一行的每个字符都是唯一的),分别表示二叉树的先序遍历和中序遍历的序列。
【输出格式】
行数等于该树的结点数,每行的字母相同。
【数据范围】
输入字符串的长度均不超过26。
【输入样例】
ABCDEFG
CBDAFEG
【输出样例】
AAAA
BB
C
D
EE
F
G
【算法分析】
利用下图中的中序、后序遍历示意图,计算x、y值的过程,可参考确立下文代码中的参数。其中:
ile:中序遍历左端点位置,iri:中序遍历右端点位置
ple:后序遍历左端点位置,pri:后序遍历右端点位置

【算法代码】
#include <bits/stdc++.h>
using namespace std;string pre,in;
int a[30];int dfs(int l1, int r1, int l2, int r2) { //preorder & inorderif(l1==r1) {a[l1]=1;return a[l1];}int k=in.find(pre[l1]);if(k>l2) a[l1]+=dfs(l1+1,l1+k-l2,l2,k-1);if(k<r2) a[l1]+=dfs(l1+k-l2+1,r1,k+1,r2);return a[l1];
}int main() { cin>>pre>>in;dfs(0,pre.size()-1,0,in.size()-1);for(int i=0; i<pre.size(); i++) {for(int j=0; j<a[i]; j++)cout<<pre[i];cout<<endl;}return 0;
}/*
in:
ABCDEFG
CBDAFEGout:
AAAA
BB
C
D
EE
F
G
*/
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/119108633
https://www.acwing.com/solution/content/184637/
相关文章:
AcWing 1260:二叉树输出
【题目来源】https://www.acwing.com/problem/content/1262/【题目描述】 树的凹入表示法主要用于树的屏幕或打印输出,其表示的基本思想是兄弟间等长,一个结点的长度要不小于其子结点的长度。 二叉树也可以这样表示,假设叶结点的长度为 1&…...
刷爆leetcode第十期
题目一 相同的树 给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 首先我们要来判断下它们的根是否相等 根相等的话是否它们的左子树相等 是否…...
Python28-7.5 降维算法之t-分布邻域嵌入t-SNE
t-分布邻域嵌入(t-distributed Stochastic Neighbor Embedding,t-SNE)是一种用于数据降维和可视化的机器学习算法,尤其适用于高维数据的降维。t-SNE通过将高维数据嵌入到低维空间(通常是二维或三维)中&…...
一个最简单的comsol斜坡稳定性分析例子——详细步骤
一个最简单的comsol斜坡稳定性分析例子——详细步骤 标准模型例子—详细步骤 线弹性模型下的地应力平衡预应力与预应变、土壤塑性和安全系数求解的辅助扫描...
Java 变量类型
在Java中,变量类型包括基本数据类型和引用数据类型,每种类型有其特定的用途和存储方式。 ### 1. 基本数据类型 Java的基本数据类型包括整数类型、浮点类型、字符类型和布尔类型,它们分别是: - **整数类型**:用于存储…...
【排序算法】—— 快速排序
快速排序的原理是交换排序,其中qsort函数用的排序原理就是快速排序,它是一种效率较高的不稳定函数,时间复杂度为O(N*longN),接下来就来学习一下快速排序。 一、快速排序思路 1.整体思路 以升序排序为例: (1)、首先随…...
前端JS特效第22波:jQuery滑动手风琴内容切换特效
jQuery滑动手风琴内容切换特效,先来看看效果: 部分核心的代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xm…...
redis的数据类型对应的使用场景
Redis提供了多种数据类型,每种数据类型都有其特定的适用场景。以下是Redis主要数据类型及其典型应用场景:1. 字符串(String) 应用场景:适用于存储简单的键值对数据,如用户基本信息、计数器(如网页访问次数&…...
ctfshow-web入门-命令执行(web118详解)Linux 内置变量与Bash切片
输入数字和小写字母,回显 evil input 查看源码,发现这里会将提交的参数 code 传给 system 函数 使用 burpsuite 抓包进行单个字符的模糊测试 fuzz: 发现过滤掉了数字和小写字母以及一些符号,下面框起来的部分是可用的 结合题目提…...
C语言 指针和数组——指针和二维数组之间的关系
目录 换个角度看二维数组 指向二维数组的行指针 按行指针访问二维数组元素 再换一个角度看二维数组 按列指针访问二维数组元素 二维数组作函数参数 指向二维数组的行指针作函数参数 指向二维数组的列指针作函数参数编辑 用const保护你传给函数的数据 小结 换个角度看…...
问题集锦1
01.inner中使用JwtTokenUtil.getUserCode() 前端调用上传(java),上传使用加购 Overridepublic Boolean insertShoppingCart(InsertShoppingCartParamsDto dto) {// 通过userCode,itemCode和supplierCode来判断当前加购人添加到购物车的商品是…...
浅析MySQL-索引篇01
什么是索引? 索引是帮助存储引擎快速获取数据的一种数据结构,类似于数据的目录。 索引的分类 按数据结构分类: MySQL 常见索引有 BTree 索引、HASH 索引、Full-Text 索引。 Innodb是MySQL5.5之后的默认存储引擎,BTree索引类型也…...
2028年企业云存储支出翻倍,达到1280亿美元
根据Omdia的研究,到2028年,企业云存储支出将从去年的570亿美元翻一番以上,达到1280亿美元。该研究分析了基础设施即服务(IaaS)和平台即服务(PaaS)数据中心的收入,作为年度存储数据服…...
ActiViz中的颜色映射表vtkLookupTable
文章目录 一、简介二、VtkLookupTable的创建与初始化三、设置数据范围四、颜色映射设置五、不透明度设置六、自定义颜色映射七、 不连续性颜色映射八、 预设颜色映射方案九、可视化效果优化十、与其他VTK组件的整合十一、 动态调整映射表十二、保存和加载颜色映射表一、简介 V…...
【Spring AOP 源码解析前篇】什么是 AOP | 通知类型 | 切点表达式| AOP 如何使用
前言(关于源码航行) 在准备面试和学习的过程中,我阅读了还算多的源码,比如 JUC、Spring、MyBatis,收获了很多代码的设计思想,也对平时调用的 API 有了更深入的理解;但过多散乱的笔记给我的整理…...
Laravel HTTP客户端:网络请求的瑞士军刀
标题:Laravel HTTP客户端:网络请求的瑞士军刀 Laravel的HTTP客户端是一个功能强大的工具,它提供了一种简洁、直观的方式来发送HTTP请求。无论是与外部API集成,还是进行网络数据抓取,Laravel的HTTP客户端都能满足你的需…...
7月07日,每日信息差
第一、6 月份,北京、上海、广州和深圳的新建商品住宅成交量分别环比增加 21%、66%、48% 和 38%,均创年内新高 第二、2024 年世界人工智能大会上,上海向四家企业发放了首批无驾驶人智能网联汽车示范应用许可,这些企业可以在浦东部…...
ubuntu 网络常用命令
在Ubuntu中,有许多网络相关的常用命令。以下是一些主要命令及其用途: ifconfig:此命令用于显示和配置网络接口信息。你可以使用它来查看IP地址、子网掩码、广播地址等。 例如:ifconfig 注意:在新版本的Linux发行版中…...
Python28-7.4 独立成分分析ICA分离混合音频
独立成分分析(Independent Component Analysis,ICA)是一种统计与计算技术,主要用于信号分离,即从多种混合信号中提取出独立的信号源。ICA在处理盲源分离(Blind Source Separation,BSS࿰…...
Spring Boot与Okta的集成
Spring Boot与Okta的集成 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿!今天我们将探讨如何在Spring Boot应用中集成Okta,实现身份认证和授权的功能…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...
uniapp 开发ios, xcode 提交app store connect 和 testflight内测
uniapp 中配置 配置manifest 文档:manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号:4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...
