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 & inorder
    if(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
CBDAFEG

out:
AAAA
BB
C
D
EE
F
G
*/





【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/119108633
https://www.acwing.com/solution/content/184637/










 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/781482.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

YOLOv8改进---BiFPN特征融合

一、BiFPN原理 1.1 基本原理 BiFPN&#xff08;Bidirectional Feature Pyramid Network&#xff09;&#xff0c;双向特征金字塔网络是一种高效的多尺度特征融合网络&#xff0c;其基本原理概括分为以下几点&#xff1a; 双向特征融合&#xff1a;BiFPN允许特征在自顶向下和自…

【驱动篇】龙芯LS2K0300之PWM设备驱动

实验目的 利用脉冲调制效应&#xff08;PWM&#xff09;等效改变输出功率大小控制LED&#xff0c;从而实现呼吸灯效果&#xff0c;需要用到RGB LED模块 模块连接 IO 插针接口上一共集成了两路PWM&#xff0c;分别是PWM2和PWM3&#xff0c;对应GPIO88、GPIO89 PWM2和PWM3对…

【Spring Cloud】一个例程快速了解网关Gateway的使用

Spring Cloud Gateway提供了一个在Spring生态系统之上构建的API网关&#xff0c;包括&#xff1a;Spring 5&#xff0c;Spring Boot 2和Project Reactor。Spring Cloud Gateway旨在提供一种简单而有效的路由方式&#xff0c;并为它们提供一些网关基本功能&#xff0c;例如&…

centos7.9 rpm包安装mysql8.2.0数据库、root设置客户端登录、配置并发、表名大小写敏感、启动重启指令等记录

centos安装mysql8数据库,下载的是rpm-bundle.tar包,这样可以在内网环境离线安装,工作中医院的服务器很多也是内网的,所以这里记录下rpm-bundle.tar包安装的步骤。 lscpu 查看处理器是x86还是arm 下载对应的版本 bundle tar包 ((mysql-8.2.0-1.el7.x86_64.rpm-bundle.tar))…

实验五 图像增强—空域滤波

一、实验目的 了解图像平滑滤波器&#xff08;均值滤波和中值滤波&#xff09;和图像锐化算子&#xff08;Sobel算子、Prewitt算子、Laplacian算子&#xff09;在工程领域中的应用&#xff1b;理解图像平滑滤波器和图像锐化算子的工程应用范围&#xff1b;掌握图像平滑滤波器和…

MSPM0G3507——编码器控制速度

绿色设置的为目标值100&#xff0c;红色为编码器实际数据 。 最后也是两者合在了一起&#xff0c;PID调试成功。 源码直接分享&#xff0c;用的是CCStheia&#xff0c;KEIL打不开。大家可以看一下源码的思路&#xff0c;PID部分几乎不用改 链接&#xff1a;https://pan.baid…

微信公众平台测试账号本地微信功能测试说明

使用场景 在本地测试微信登录功能时&#xff0c;因为微信需要可以互联网访问的域名接口&#xff0c;所以本地使用花生壳做内网穿透&#xff0c;将前端服务的端口和后端服务端口进行绑定&#xff0c;获得花生壳提供的两个外网域名。 微信测试账号入口 绑定回调接口 回调接口的…

C++左值右值

在C中&#xff0c;左值&#xff08;lvalue&#xff09;和右值&#xff08;rvalue&#xff09;是表达式分类的关键概念&#xff0c;它们主要影响表达式的赋值、函数调用以及操作符的使用方式。这些概念在C11及以后的版本中变得更加重要&#xff0c;因为引入了移动语义和右值引用…

字符串和正则表达式踩坑

// 中石化加油卡号格式&#xff1a;以 100011 开头共19位public static final String ZHONGSHIYOU_OIL_CARD_PATTERN "^100011\\d{13}$";// 中石油加油卡号格式&#xff1a;以90、95、70开头共16位public static final String ZHONGYOU_OIL_CARD_PATTERN "^(9…

按键控制LED流水灯模式定时器时钟

目录 1.定时器 2. STC89C52定时器资源 3.定时器框图 4. 定时器工作模式 5.中断系统 1&#xff09;介绍 2&#xff09;流程图&#xff1a;​编辑 3&#xff09;STC89C52中断资源 4&#xff09;定时器和中断系统 5&#xff09;定时器的相关寄存器 6.按键控制LED流水灯模…

去O化神器 Exbase

随着去O化进程推动&#xff0c;很多旧业务依赖的oracle数据库&#xff0c;都需要实现做数据库的替换&#xff0c;当下能很好兼容Oracle&#xff0c;并实现异构数据库之间转换的工具并不多。这里给大家推荐一个商业工具数据库迁移工具exbase&#xff08;北京海量&#xff09;&am…

谷粒商城学习笔记-17-快速开发-逆向工程搭建使用

文章目录 一&#xff0c;克隆人人开源的逆向工程代码二&#xff0c;把逆向工程集成到谷粒商城的后台工程三&#xff0c;以商品服务为例&#xff0c;使用逆向工程生成代码1&#xff0c;修改逆向工程的配置2&#xff0c;以Debug模式启动逆向工程3&#xff0c;使用逆向工程生成代码…

通信协议_C#实现自定义ModbusRTU主站

背景知识&#xff1a;modbus协议介绍 相关工具 mbslave:充当从站。虚拟串口工具:虚拟出一对串口。VS2022。 实现过程以及Demo 打开虚拟串口工具: 打开mbslave: 此处从站连接COM1口。 Demo实现 创建DLL库&#xff0c;创建ModbusRTU类,进行实现&#xff1a; using Syste…

OpenAI的崛起:从梦想到现实

OpenAI的崛起不仅是人工智能领域的重大事件&#xff0c;也是科技史上一个引人注目的篇章。本文将深入探讨OpenAI从创立到如今的演变过程&#xff0c;分析其成功的关键因素&#xff0c;以及未来的发展方向。 一、OpenAI的初创期&#xff1a;理想主义与混乱并存 OpenAI成立于20…

【74CH160组成60进制0-59】2021-11-22

缘由60进制计数 到达60后显示ff-嵌入式-CSDN问答 缘由《数电》用两片74160接成29进制计数器应该怎么接呢&#xff1f;-嵌入式-CSDN问答

解决数据库PGSQL,在Mybatis中创建临时表报错TODO IDENTIFIER,连接池用的Druid。更换最新版本Druid仍然报错解决

Druid版本1.1.9报错Caused by: java.sql.SQLException: sql injection violation, syntax error: TODO IDENTIFIER : CREATE TEMPORARY TABLE temp_ball_classify (id int8 NOT NULL,create_time TIMESTAMP,create_by VARCHAR,classify_name VARCHAR) 代码如下&#xff1a; 测…

【数据结构与算法】快速排序双指针法

&#x1f493; 博客主页&#xff1a;倔强的石头的CSDN主页 &#x1f4dd;Gitee主页&#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏&#xff1a;《数据结构与算法》 期待您的关注 ​

STM32实战项目:从零打造GPS蓝牙自行车码表,掌握传感器、蓝牙、Flash存储等核心技术

一、 引言 骑行&#xff0c;作为一项绿色健康的运动方式&#xff0c;越来越受到人们的喜爱。而记录骑行数据&#xff0c;分析速度、里程等信息&#xff0c;则成为了许多骑行爱好者的追求。本篇文章将带你使用STM32单片机&#xff0c;DIY一款功能完备的自行车码表&#xff0c;记…

【开放集目标检测】Grounding DINO

一、引言 论文&#xff1a; Grounding DINO: Grounding DINO: Marrying DINO with Grounded Pre-Training for Open-Set Object Detection 作者&#xff1a; IDEA 代码&#xff1a; Grounding DINO 注意&#xff1a; 该算法是在Swin Transformer、Deformable DETR、DINO基础上…

【LeetCode】有效的数独

目录 一、题目二、解法 一、题目 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 &#xff0c;验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。&…