/*用递归的思想，后序输出的最后一个元素必定是树的根节点，记为key，然后在中序输出中可以找到 key 。在中序输出中，key左边为左子树（长度为alen），右边为右子树（长度为blen），后序输出中也有左子树（长度与alen一样，没错，就是前alen个元素），而右子树为后blen个元素（除了key，就是根节点），再将中序与后序中的左子树递归下去，右子树递归下去，当alen=blen=0时，结束递归即可，（注意alen必定=blen）*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
void cpy(char it[], char from[], int n)//复制左子树或右子树
{
for (int i = 0; i < n; i++)
it[i] = from[i];
it[n] = '\0';
}
void change(char ldrl[], char ldrr[], char lrdl[], char lrdr[], char ldr[], char lrd[])
{
int alen = strlen(ldr);
int blen = strlen(lrd);
int left = 0, right = 0;
char key = lrd[blen - 1];//key为这棵树的根节点的值
while (ldr[left] != key)//判断根节点左边有多少节点
left++;
right = alen - left - 1;//从树的节点数和左节点数求得右节点数，方便下边的复制
cpy(ldrl, ldr, left);
cpy(lrdl, lrd, left);
cpy(ldrr, ldr + left + 1, right);
cpy(lrdr, lrd + left, right);
}
void handle(char ldr[], char lrd[])
{
int alen = strlen(ldr);
int blen = strlen(lrd);
if (blen == 0) return;//alen和blen必定是相等的，因为相同的树所含节点相同，所以blen=0时，必定无节点可输出，此时返回即可
cout << lrd[blen - 1];//输出根节点
char ldrl[20], ldrr[20], lrdl[20], lrdr[20];
change(ldrl, ldrr, lrdl, lrdr,ldr,lrd);
handle(ldrl, lrdl);//将左子树递归下去
handle(ldrr, lrdr);//将右子树递归下去
}
int main()
{
char ldr[20], lrd[20];
cin >> ldr >> lrd;
handle(ldr, lrd);
system("pause");
return 0;
}

感谢题解大牛
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN=10;
char in_order[MAXN];
char post_order[MAXN];
char pre_order[MAXN];
void build(int l1,int r1,int l2,int r2)
{
if(l1>r1||l2>r2)
return ;
char root=post_order[r2];
int p=l1;
while(in_order[p]!=root) p++;
printf("%c",root);
int cnt=p-l1;
build(l1,p-1,l2,l2+cnt-1);
build(p+1,r1,l2+cnt,r2-1);
}
int main()
{
scanf("%s",in_order);
scanf("%s",post_order);
int len=strlen(in_order);
build(0,len-1,0,len-1);

return 0;
}

#include<cstdio>
int o1[15],o2[15],o3[15];
int num(char a)
{
    return a-'A'+1;
}
char let(int a)
{
    return a+'A'-1;
}
void build(int l,int r,int L,int R)
{
    int root=o2[R];
    int i;
    for (i=1;o1[i]!=root;i++);
    printf("%c",let(root));
    if (i!=l)
    {
        build(l,i-1,L,i-l+L-1);
    }
    if (i!=r)
    {
        build(i+1,r,R-r+i,R-1);
    }
}
int main()
{
    freopen("c.in","r",stdin);
    char s[15];
    scanf("%s",s+1);
    int i;
    for(i=1;s[i]>='A';i++)
    {
        o1[i]=num(s[i]);
    }
    int len=i-1;
    scanf("%s",s+1);
    for(i=1;s[i]>='A';i++)
    {
        o2[i]=num(s[i]);
    }
    build (1,len,1,len);
    return 0;
}

感觉被逗了，这道题明明很简单。。。
搞一个才c[i]，值为j，意为在中序遍历中第i个节点在后序遍历中的位置为j。
那么j越大，越接近根。
所以先输出根，然后在做左边，然后右边，用递归。
procedure play(l,r:longint);
var
i,j,t,max,bi:longint;
begin
if l>r then exit;
if l=r then
begin
write(a[l]);
exit;
end;
max:=0;
bi:=L;
for i:=L to R do if max<c[i] then//找出最大的，即为最接近根节点的，第一次肯定是根(后序遍历)
begin
max:=c[i];
bi:=i;
end;
write(A[BI]);
play(L,bi-1);
play(bi+1,r);
end;
编译成功

Free Pascal Compiler version 2.6.2 [2013/02/12] for i386
Copyright (c) 1993-2012 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(7,11) Note: Local variable "j" not used
foo.pas(7,13) Note: Local variable "t" not used
foo.pas(2,13) Note: Local variable "k" not used
foo.pas(2,15) Note: Local variable "o" not used
foo.pas(2,17) Note: Local variable "p" not used
foo.pas(2,19) Note: Local variable "n" not used
Linking foo.exe
34 lines compiled, 0.2 sec , 27136 bytes code, 1628 bytes data
6 note(s) issued
测试数据 #0: Accepted, time = 0 ms, mem = 688 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 692 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 692 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 688 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 688 KiB, score = 10
Accepted, time = 15 ms, mem = 692 KiB, score = 50
感觉好多东西都没用上

记录信息
评测状态 Accepted
题目 P1132 求二叉树的先序序列
递交时间 2015-10-11 19:49:22
代码语言 C++
评测机 VijosEx
消耗时间 56 ms
消耗内存 16200 KiB
评测时间 2015-10-11 19:49:24
评测结果
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 16196 KiB, score = 10
测试数据 #1: Accepted, time = 13 ms, mem = 16196 KiB, score = 10
测试数据 #2: Accepted, time = 14 ms, mem = 16200 KiB, score = 10
测试数据 #3: Accepted, time = 14 ms, mem = 16200 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 16196 KiB, score = 10
Accepted, time = 56 ms, mem = 16200 KiB, score = 50
代码
#include <iostream>
#include <string.h>
#include <sstream>
#include <stdio.h>
#include <algorithm>
using namespace std;

const int maxn=1001000;
int in_order[maxn],post_order[maxn],lch[maxn],rch[maxn];
int n;

void read_list(int *a)
{
char line[10];
scanf("%s",line);
n=0;
int x=-1;
while(line[++x]<='Z'&&line[x]>='A')a[n++]=line[x]-'A'+1;
return;
}

int build(int L1,int R1,int L2,int R2)
{
if(L1>R1)return 0;
int root=post_order[R2];
int p=L1;
while(in_order[p]!=root)p++;
int cnt=p-L1;
lch[root]=build(L1,p-1,L2,L2+cnt-1);
rch[root]=build(p+1,R1,L2+cnt,R2-1);
return root;
}
void print(int node)
{
printf("%c",node-1+'A');
if(lch[node])print(lch[node]);
if(rch[node])print(rch[node]);
}
int main()
{
read_list(in_order);
read_list(post_order);
build(0,n-1,0,n-1);
print(post_order[n-1]);
}

program exercise(input,output);
var n:longint;
s1,s2:string;
f:array[1..26]of char;
l,r:array[1..26]of longint;
procedure print(x:longint);
begin
write(f[x]);
if l[x]>0 then
print(l[x]);
if r[x]>0 then
print(r[x]);
end;
procedure find(s1,s2:string);
var x,y:longint;
begin
inc(n);
f[n]:=s1[length(s1)];
y:=n;
x:=pos(s1[length(s1)],s2);
if x>1 then
begin
l[y]:=n+1;
find(copy(s1,1,x-1),copy(s2,1,x-1));
end;
if x<length(s2) then
begin
r[y]:=n+1;
find(copy(s1,x,length(s2)-x),copy(s2,x+1,length(s2)-x));
end;
end;
begin
readln(s2);
readln(s1);
n:=0;
find(s1,s2);
print(1);
end.

分析样例可以发现
1.后序遍历根是在最后的，样例中，A在最后，所以说A就是这棵树的根
2.找到A在中序遍历中的位置，A左边的字母就是A的左子树，A右边的字母就是A的右子树
3.递归A的左右子树，就像处理A一样 。

var
a,b:string;
l,i,j:longint;
c:array[0..100] of longint; //c[i]表示中序遍历中的i在后序遍历中的位置，c[i]越大，i就越靠近根
procedure did(l,r:longint); //处理l到r的区间
var max,i,p:longint;

begin
if l>r then exit;
if l=r then begin write(a[l]); exit; end;
p:=l;
max:=0;
for i:=l to r do
if c[i]>max then begin max:=c[i]; p:=i; end;
write(a[p]);
did(l,p-1);
did(p+1,r);
end;
begin
readln(a);
readln(b);
l:=length(a);
for i:=1 to l do //预处理出中序遍历中的每个点在后序遍历中的位置
for j:=1 to l do
if (a[i]=b[j]) then c[i]:=j;
did(1,l);
end.

program tree01;

var z,h: string;

procedure find(a,b:string);
var s,l : integer;
begin
l:=length(b);
if l=1 then Write(b)
else
begin
Write(b[l]);
s:=pos(b[l],a);
if s-1>0 then find(copy(a,1,s-1),copy(b,1,s-1));
if l-s>0 then find(copy(a,s+1,l-s),copy(b,s,l-s));
end;
end;
begin
Readln(z);
Readln(h);
Find(z,h);
Readln;
end.

无需建树，直接在后序遍历和中序遍历中找到树根递归求解即可
void solve(string in,string post) {
if (post.empty()) return;
char root=post[post.size()-1];
cout<<root;
int n=0;
while (in[n]!=root) ++n;
solve(in.substr(0,n),post.substr(0,n));
solve(in.substr(n+1,in.size()-n-1),post.substr(n,in.size()-n-1));
}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN=10;

char z[MAXN], h[MAXN];

void dfs(int a, int b, int c, int d){
if(a > b)
return ;
cout<<h[d];

for(int i=a; i<=b; i++)
if(z[i] == h[d]){
dfs(a, i-1, c, c+i-1-a);
dfs(i+1, b, c+i-a, d-1);

}

}

int main()
{
cin>>z;
cin>>h;
dfs(0, strlen(z)-1, 0, strlen(z)-1);
system("pause");
return 0;
}
水一发。。。

#include<iostream>
using namespace std;
char zhong[10];
char hou[10];
void go(int zf,int zt,int hf,int ht){
int i;
for (i = zf; i <= zt;i++)
if (zhong[i] == hou[ht])
break;
cout << hou[ht];
if (i > zf){
go(zf, i - 1, hf, hf + (i - 1) - zf);
}
if (i < zt){
go(i + 1, zt, ht-1 - (zt - (i + 1)), ht - 1);
}
}
int main(){
freopen("in.txt", "r", stdin);
cin >> zhong >> hou;
int i;
for (i = 0; hou[i] != 0; i++);
go(0,i-1,0,i-1);
return 0;
}

var
pre,mid,post:string;

procedure f(mid,post:string);
var
i:integer;
begin
if (mid='') or (post='') then
exit;
i:=pos(post[length(post)],mid);
pre:=pre+post[length(post)];
f(copy(mid,1,i-1),copy(post,1,i-1));
f(copy(mid,i+1,length(mid)-i),copy(post,i,length(post)-i));
end;

begin
readln(mid);
readln(post);
f(mid,post);
writeln(pre);
end.//By Fkc

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char mid[10], back[10];
int len;
void solve(char root, int l, int r)
{

if (l <= r)
{ printf("%c", root);
int p, q;
for (int i = len-1; i >= 0; i--)
if (mid[i] == root){ p = i; break;}
for (int i = len-1; i >= 0; i--)

if (back[i] == root) { q = i; break;}

solve(back[q-r+p-1], l, p-1);
solve(back[q-1], p+1, r);
}
}

int main()
{ scanf("%s", mid);
scanf("%s", back);
len = strlen(mid);
solve(back[len-1], 0, len-1);
printf("\n");
return 0;
}

#include<cstdio>
#include<cstring>
char m[9]={0},b[9]={0};
void dfs(int ms,int me,int bs,int be){
int mr;
for(mr=ms;mr<=me&&m[mr]!=b[be];mr++);
printf("%c",m[mr]);
if(mr!=ms)dfs(ms,mr-1,bs,bs+mr-ms-1);else;
if(mr!=me)dfs(mr+1,me,bs+mr-ms,be-1);else;
}
int main(){
freopen("P1132.in","r",stdin);
freopen("P1132.out","w",stdout);
scanf("%s\n%s\n",m,b);
dfs(0,strlen(m)-1,0,strlen(b)-1);
printf("\n");
}

我用递归切分法，虽多4行，but也AC!!!

#include<iostream>
#include<cstring>
using namespace std;
void tr(int sta,int end,char *a,char *b)
{
int i,j,k,l;
if(end-sta>=0)
{
for(i=sta;i<=end;i++)if(a[i]==b[end])j=i;
cout<<b[end];
for(i=end;i>=j+1;i--)b[i]=b[i-1];
tr(sta,j-1,a,b);
tr(j+1,end,a,b);
}
}
int main()
{
char a[9],b[9];
cin>>a>>b;
int la=strlen(a);
tr(0,la-1,a,b);
cout<<endl;
return 0;
}

http://blog.csdn.net/u012746396/article/details/19935205
不喜勿喷

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
int find(int l,char *a,char *b){
if(l)
for(int i=l;i>=1;i--)

if(a[i]==b[l]){
printf("%c",a[i]);
find(i-1,a,b);
find(l-i,a+i,b+i-1);
}
}
int main(){
char a[1000],b[1000];
scanf("%s %s",a+1,b+1);
int ln=strlen(a+1);
find(ln,a,b);
return 0;
}

http://hi.baidu.com/fcamtrhdnoafpse/item/b12a222bafaf822076272c29

var a,b:string;
procedure aa(n:string);
var i,j,k,l:longint;
begin
write(n[length(n)]);if length(n)=1 then exit;
i:=pos(copy(n,length(n),1),a);j:=i;
while (j>1)and(pos(copy(a,j-1,1),n)>0) do dec(j);
if i>j then aa(copy(n,1,i-j));
if i-j<length(n)-1 then aa(copy(n,i-j+1,length(n)-1-i+j));
end;
begin
readln(a);readln(b);
aa(b);
writeln;
end.
遍历嘛

纯递归就行var i,j,k,l,n,m:longint;
s1,s2:string;

procedure try(s1,s2:string);
var i,t:longint;
begin
t:=0;
write(s2[length(s2)]);
for i:=1 to length(s1) do if s1[i]=s2[length(s2)] then begin
t:=i;
break;
end;
if t>1 then try(copy(s1,1,t-1),copy(s2,1,t-1));
if t<length(s1) then try(copy(s1,t+1,length(s1)-t+1),copy(s2,t,length(s2)-t ));
end;

begin
readln(s1);
readln(s2);
try(s1,s2);
end.