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

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/【题目描述】 树的凹入表示法主要用于树的屏幕或打印输出&#xff0c;其表示的基本思想是兄弟间等长&#xff0c;一个结点的长度要不小于其子结点的长度。 二叉树也可以这样表示&#xff0c;假设叶结点的长度为 1&…...

刷爆leetcode第十期

题目一 相同的树 给你两棵二叉树的根节点 p 和 q &#xff0c;编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同&#xff0c;并且节点具有相同的值&#xff0c;则认为它们是相同的。 首先我们要来判断下它们的根是否相等 根相等的话是否它们的左子树相等 是否…...

Python28-7.5 降维算法之t-分布邻域嵌入t-SNE

t-分布邻域嵌入&#xff08;t-distributed Stochastic Neighbor Embedding&#xff0c;t-SNE&#xff09;是一种用于数据降维和可视化的机器学习算法&#xff0c;尤其适用于高维数据的降维。t-SNE通过将高维数据嵌入到低维空间&#xff08;通常是二维或三维&#xff09;中&…...

一个最简单的comsol斜坡稳定性分析例子——详细步骤

一个最简单的comsol斜坡稳定性分析例子——详细步骤 标准模型例子—详细步骤 线弹性模型下的地应力平衡预应力与预应变、土壤塑性和安全系数求解的辅助扫描...

Java 变量类型

在Java中&#xff0c;变量类型包括基本数据类型和引用数据类型&#xff0c;每种类型有其特定的用途和存储方式。 ### 1. 基本数据类型 Java的基本数据类型包括整数类型、浮点类型、字符类型和布尔类型&#xff0c;它们分别是&#xff1a; - **整数类型**&#xff1a;用于存储…...

【排序算法】—— 快速排序

快速排序的原理是交换排序&#xff0c;其中qsort函数用的排序原理就是快速排序&#xff0c;它是一种效率较高的不稳定函数&#xff0c;时间复杂度为O(N*longN)&#xff0c;接下来就来学习一下快速排序。 一、快速排序思路 1.整体思路 以升序排序为例&#xff1a; (1)、首先随…...

前端JS特效第22波:jQuery滑动手风琴内容切换特效

jQuery滑动手风琴内容切换特效&#xff0c;先来看看效果&#xff1a; 部分核心的代码如下&#xff1a; <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xm…...

redis的数据类型对应的使用场景

Redis提供了多种数据类型&#xff0c;每种数据类型都有其特定的适用场景。以下是Redis主要数据类型及其典型应用场景&#xff1a;1. 字符串(String) 应用场景&#xff1a;适用于存储简单的键值对数据&#xff0c;如用户基本信息、计数器&#xff08;如网页访问次数&…...

ctfshow-web入门-命令执行(web118详解)Linux 内置变量与Bash切片

输入数字和小写字母&#xff0c;回显 evil input 查看源码&#xff0c;发现这里会将提交的参数 code 传给 system 函数 使用 burpsuite 抓包进行单个字符的模糊测试 fuzz&#xff1a; 发现过滤掉了数字和小写字母以及一些符号&#xff0c;下面框起来的部分是可用的 结合题目提…...

C语言 指针和数组——指针和二维数组之间的关系

目录 换个角度看二维数组 指向二维数组的行指针 按行指针访问二维数组元素 再换一个角度看二维数组 按列指针访问二维数组元素 二维数组作函数参数 指向二维数组的行指针作函数参数 指向二维数组的列指针作函数参数​编辑 用const保护你传给函数的数据 小结 换个角度看…...

问题集锦1

01.inner中使用JwtTokenUtil.getUserCode() 前端调用上传&#xff08;java&#xff09;&#xff0c;上传使用加购 Overridepublic Boolean insertShoppingCart(InsertShoppingCartParamsDto dto) {// 通过userCode,itemCode和supplierCode来判断当前加购人添加到购物车的商品是…...

浅析MySQL-索引篇01

什么是索引&#xff1f; 索引是帮助存储引擎快速获取数据的一种数据结构&#xff0c;类似于数据的目录。 索引的分类 按数据结构分类&#xff1a; MySQL 常见索引有 BTree 索引、HASH 索引、Full-Text 索引。 Innodb是MySQL5.5之后的默认存储引擎&#xff0c;BTree索引类型也…...

2028年企业云存储支出翻倍,达到1280亿美元

根据Omdia的研究&#xff0c;到2028年&#xff0c;企业云存储支出将从去年的570亿美元翻一番以上&#xff0c;达到1280亿美元。该研究分析了基础设施即服务&#xff08;IaaS&#xff09;和平台即服务&#xff08;PaaS&#xff09;数据中心的收入&#xff0c;作为年度存储数据服…...

ActiViz中的颜色映射表vtkLookupTable

文章目录 一、简介二、VtkLookupTable的创建与初始化三、设置数据范围四、颜色映射设置五、不透明度设置六、自定义颜色映射七、 不连续性颜色映射八、 预设颜色映射方案九、可视化效果优化十、与其他VTK组件的整合十一、 动态调整映射表十二、保存和加载颜色映射表一、简介 V…...

【Spring AOP 源码解析前篇】什么是 AOP | 通知类型 | 切点表达式| AOP 如何使用

前言&#xff08;关于源码航行&#xff09; 在准备面试和学习的过程中&#xff0c;我阅读了还算多的源码&#xff0c;比如 JUC、Spring、MyBatis&#xff0c;收获了很多代码的设计思想&#xff0c;也对平时调用的 API 有了更深入的理解&#xff1b;但过多散乱的笔记给我的整理…...

Laravel HTTP客户端:网络请求的瑞士军刀

标题&#xff1a;Laravel HTTP客户端&#xff1a;网络请求的瑞士军刀 Laravel的HTTP客户端是一个功能强大的工具&#xff0c;它提供了一种简洁、直观的方式来发送HTTP请求。无论是与外部API集成&#xff0c;还是进行网络数据抓取&#xff0c;Laravel的HTTP客户端都能满足你的需…...

7月07日,每日信息差

第一、6 月份&#xff0c;北京、上海、广州和深圳的新建商品住宅成交量分别环比增加 21%、66%、48% 和 38%&#xff0c;均创年内新高 第二、2024 年世界人工智能大会上&#xff0c;上海向四家企业发放了首批无驾驶人智能网联汽车示范应用许可&#xff0c;这些企业可以在浦东部…...

ubuntu 网络常用命令

在Ubuntu中&#xff0c;有许多网络相关的常用命令。以下是一些主要命令及其用途&#xff1a; ifconfig&#xff1a;此命令用于显示和配置网络接口信息。你可以使用它来查看IP地址、子网掩码、广播地址等。 例如&#xff1a;ifconfig 注意&#xff1a;在新版本的Linux发行版中…...

Python28-7.4 独立成分分析ICA分离混合音频

独立成分分析&#xff08;Independent Component Analysis&#xff0c;ICA&#xff09;是一种统计与计算技术&#xff0c;主要用于信号分离&#xff0c;即从多种混合信号中提取出独立的信号源。ICA在处理盲源分离&#xff08;Blind Source Separation&#xff0c;BSS&#xff0…...

Spring Boot与Okta的集成

Spring Boot与Okta的集成 大家好&#xff0c;我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01;今天我们将探讨如何在Spring Boot应用中集成Okta&#xff0c;实现身份认证和授权的功能…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

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

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

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...