题目描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度\le 8≤8）。
输入输出格式
输入格式：
22行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。
输出格式：
11行，表示一棵二叉树的先序。
输入输出样例
输入样例#1：
复制
BADC BDCA
输出样例#1：
复制
View Code
View Code
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-1,l2,l2+cnt-1); build(p+1,r,l2+cnt,r2-1); } int main() { char s[10]; RS(s); rep(i,0,strlen(s)) zhong[i]=s[i]; RS(s); rep(i,0,strlen(s)) hou[i]=s[i]; int len=strlen(s); build(0,len-1,0,len-1); }
大佬的做法
#include<cstdio> #include<iostream> #include<cstring> using namespace std; void beford(string in,string after){ if (in.size()>0){ char ch=after[after.size()-1]; cout<<ch;//找根输出 int k=in.find(ch); beford(in.substr(0,k),after.substr(0,k)); beford(in.substr(k+1),after.substr(k,in.size()-k-1));//递归左右子树； } } int main(){ string inord,aftord; cin>>inord;cin>>aftord;//读入 beford(inord,aftord);cout<<endl; return 0; }
题目描述
输入一串二叉树，用遍历前序打出。
输入输出格式
输入格式：
第一行为二叉树的节点数n。(n \leq 26n≤26)
后面n行，每一个字母为节点，后两个字母分别为其左右儿子。
空节点用*表示
输出格式：
前序排列的二叉树
输入输出样例
输入样例#1：
复制
6 abc bdi cj* d** i** j**
输出样例#1：
复制
View Code
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[10]; while(n--) { RS(s); vis[s[0]]=1; vis[s[1]]=1; vis[s[2]]=1; if(s[1]!='*') { l[s[0]]=s[1]; cnt[s[1]]++; } if(s[2]!='*') { r[s[0]]=s[2]; cnt[s[2]]++; } } int root; rep(i,'a','z') if(vis[i]&&!cnt[i]) { root=i;break; } print(root); }