题目描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度\le 8≤8）。
输入输出格式
输入格式：
22行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。
输出格式：
11行，表示一棵二叉树的先序。
输入输出样例
输入样例#1： 复制
BADC
BDCA
输出样例#1： 复制
ABCD 虽然这是一道我做过第三次类似的题目的题了 优化:
可以不用print函数来打印
直接在建树里面打印
#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
#define inf 2147483647
#define N 500000+50
int zhong[N];
int hou[N]; void build(int l,int r,int l2,int r2)
{
if(l>r||l2>r2)return ;
int root=hou[r2];
int p=l;
while(zhong[p]!=root)p++;
int cnt=p-l;
printf("%c",root);
build( l, p-,l2,l2+cnt-);
build(p+,r,l2+cnt,r2-); }
int main()
{
char s[];
RS(s);
rep(i,,strlen(s))
zhong[i]=s[i];
RS(s);
rep(i,,strlen(s))
hou[i]=s[i];
int len=strlen(s);
build(,len-,,len-);
}
大佬的做法
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
void beford(string in,string after){
if (in.size()>){
char ch=after[after.size()-];
cout<<ch;//找根输出
int k=in.find(ch);
beford(in.substr(,k),after.substr(,k));
beford(in.substr(k+),after.substr(k,in.size()-k-));//递归左右子树；
}
}
int main(){
string inord,aftord;
cin>>inord;cin>>aftord;//读入
beford(inord,aftord);cout<<endl;
return ;
}
题目描述
输入一串二叉树，用遍历前序打出。
输入输出格式
输入格式：
第一行为二叉树的节点数n。(n \leq 26n≤26)
后面n行，每一个字母为节点，后两个字母分别为其左右儿子。
空节点用*表示
输出格式：
前序排列的二叉树
输入输出样例
输入样例#1： 复制
6
abc
bdi
cj*
d**
i**
j**
输出样例#1： 复制
abdicj 沦落为做水题了 真是尴尬
#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
#define inf 2147483647
#define N 200
int l[N];
int r[N];
int vis[N];
int cnt[N];
void print(int x)
{
if(!x)return ;
if(x=='*')return ;
printf("%c",x);
print(l[x]);
print(r[x]);
return ;
}
int main()
{
int n;
RI(n);
char s[];
while(n--)
{
RS(s);
vis[s[]]=;
vis[s[]]=;
vis[s[]]=;
if(s[]!='*')
{
l[s[]]=s[];
cnt[s[]]++;
}
if(s[]!='*')
{
r[s[]]=s[];
cnt[s[]]++;
}
}
int root;
rep(i,'a','z')
if(vis[i]&&!cnt[i])
{
root=i;break;
}
print(root);
}