UVa 536 Tree Recovery
2024-08-21 18:34:29
题意:给出一颗二叉树的前序遍历和中序遍历,输出其后序遍历
用杭电1710的代码改一点,就可以了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<algorithm>
using namespace std; typedef long long LL;
const int maxn=;
char a[maxn],b[maxn],ans[maxn],s1[maxn],s2[maxn]; void build(int n,char *s1,char *s2,char *s){
if(n<=) return;
int p;
for(int i=;i<n;i++){
if(s2[i]==s1[]){
p=i;//在中序遍历中找到根结点的位置
break;
}
} build(p,s1+,s2,s);//p为左子树的区间长度,s1+1是在前序遍历中左子树的开头,s2是在中序遍历中左子树的开头
build(n-p-,s1+p+,s2+p+,s+p);//n-p-1为右子树的区间长度,s1+p+1 是在前序遍历中右子树的开头,s2是在中序遍历中右子树的开头
s[n-]=s1[];
} int main()
{
int n,i;
while(cin>>a>>b){
for(i=;i<strlen(a);i++) s1[i]=a[i];
for(i=;i<strlen(b);i++) s2[i]=b[i];
n=strlen(a);
build(n,s1,s2,ans);
for(i=;i<n-;i++) printf("%c",ans[i]);
printf("%c\n",ans[i]);
}
return ;
}
最新文章
- 转载----How fast is Redis?
- 在lua脚本中使用我们自定义的精灵类
- C#部分的总结
- songtaste网站歌曲真实URL获取
- python模块以及导入出现ImportError: No module named &#39;xxx&#39;问题
- POJ 2393 贪心 简单题
- Android 设定activity的进入和退出效果
- 【转】 std list/vector sort 排序
- 关于SSH框架设计的一些理解
- Programming In Scala笔记-第七章、Scala中的控制结构
- leetcode — best-time-to-buy-and-sell-stock-iii
- WPF StringFormat 格式化文本
- SpringCloud教程 | 第二篇: 服务消费者(rest+ribbon)
- Codeforces Codeforces Round #484 (Div. 2) D. Shark
- 如何征服面试官,拿到Offer [转]
- Xilinx 常用模块汇总(verilog)【01】
- HDU1003 最大子段和 线性dp
- 一个Golang例子:for + goroutine + channel
- 7-n!的位数(斯特灵公式)
- C语言的存储类型和关键字extern、static
热门文章
- asp.net中的mysql传参数MySqlParameter
- Text selection in div(contenteditable) when double click
- 【BZOJ】【1029】【JSOI2007】建筑抢修
- 2012 Asia JinHua Regional Contest
- [设计模式] 3 创建者模式 builder
- linux系统进程的内存布局
- cf div2 235 D
- POJ 1094 Sorting It All Out (拓扑排序,判断序列是否唯一,图是否有环)
- hdu 1370 Biorhythms
- SQL server 复习一