给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度\le 8≤8）。
输入格式：
22行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。
输出格式：
11行，表示一棵二叉树的先序。
BADC BDCA
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; }
原文：https://www.cnblogs.com/bxd123/p/10686614.html
