后续遍历的最后一项是根节点，由此可以在中序遍历中找到根节点的左右子树，注意此时后序遍历左子树序列的长度应该是等于中序遍历中的左子树序列长度，因此可以递归划分左右子树求解。注意要判断无左（右）子树的情况。

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
string a,b;
void dfs(long l1,long r1,long l2,long r2)
{
    long i;
    cout<<b[r2];
    if (l1<r1){
        for (i=l1;i<=r1;i++)
            if (a[i]==b[r2]){
                if (l1<=i-1) dfs(l1,i-1,l2,l2+i-1-l1); //left sub tree
                if (i+1<=r1)dfs(i+1,r1,l2+i-l1,r2-1); //right sub tree
                return;
            }
    }
}
main()
{
    long x;
    cin>>a>>b;
    x=a.size();
    dfs(0,x-1,0,x-1);
}

/*思路：后序遍历的最后一项就是根节点，在中序遍历中找到这个根节点的位置，然后就确定了子树在中序/后序遍历的位置，递归求解*/
#include <cstdio>
#include <cstring>
struct Tree
{
    char node;
    Tree *lson, *rson;
};

Tree *root;
char in[100],po[100];

void buildTree(Tree* &tr,int in_pos, int po_pos, int len)
{
    if (len <= 0)
    {
        tr = NULL;
        return;
    }
    tr = new Tree;
    tr->node = po[po_pos + len - 1];
    int pos = in_pos;
    for (; pos < in_pos + len; pos++)
    {
        if (in[pos] == tr->node)
        {
            break;
        }
    }
    int lsize = pos - in_pos, rsize = len - lsize - 1;
    buildTree(tr->lson,in_pos,po_pos,lsize);
    buildTree(tr->rson,pos+1,po_pos + lsize, rsize);    
}

void pre_traverse(Tree *tr)
{
    if (tr==NULL) return;
    printf("%c",tr->node);
    pre_traverse(tr->lson);
    pre_traverse(tr->rson); 
    
}




int main()
{
    scanf("%s%s",in,po);
    buildTree(root,0,0,strlen(in));
    pre_traverse(root);
}

有点简单粗暴，不过AC了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
string todlr(string ldr,string lrd){
    string dlr;
    int n = lrd.size(),dPos;
    dlr += lrd[n-1];
    if(n==1) return dlr;
    dPos = ldr.find(dlr[0]);
    if(dPos>0) dlr += todlr(ldr.substr(0,dPos),lrd.substr(0,dPos));
    if(dPos<n-1) dlr += todlr(ldr.substr(dPos+1,n-1-dPos),lrd.substr(dPos,n-1-dPos));
    return dlr;
}
int main(){
    string ldr,lrd;
    cin>>ldr>>lrd;
    cout<<todlr(ldr,lrd);
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>

using namespace std;

int zx[500]={0};
string zxs="",hxs="";

void f(int zxl,int zxr,int hxl,int hxr){
    cout<<hxs[hxr];
    if (hxl>=hxr) return;
    int i=zx[hxs[hxr]];
    if (i-1>=zxl) f(zxl,i-1,hxl,hxl+i-1-zxl);
    if (i+1<=zxr) f(i+1,zxr,hxl-zxl+i,hxr-1);
}

int main(void){
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    cin>>zxs>>hxs;
    int size=zxs.length(); 
    for (int i=0;i<size;i++){
        zx[zxs[i]]=i;
    }
    f(0,size-1,0,size-1);
    return 0;
}

先把中序遍历的字母位置进行存储，进行了小小的优化

#include<iostream>

#include<cstdio>

#include<string>

using namespace std;

string x,y;

void write(int p,int q,int m,int n)

{

if(p>q)return;

if(p==q){cout<<x[p];return;}

int i,j,k;

k=x.find(y[n]);

cout<<y[n];
write(p,k-1,m,m+k-p-1);
write(k+1,q,m+k-p,n-1);
}
int main()
{
int i,j,k;
cin>>x>>y;

k=x.length();

write(0,k-1,0,k-1);

return 0;

}

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
char a[10]={0},b[10]={0};
int n;
int bl(int x,int y,int w,int z){
if(x>y) return 0;
int l;
for(int i=x;i<=y;i++)
if(a[i]==b[z]) { l=i; break; }
printf("%c",a[l]);
bl(x,l-1,w,w+(l-1-x));
bl(l+1,y,w+l-x,z-1);
return 0;
}
int main(){
scanf("%s",a);
scanf("%s",b);
n=strlen(a);
bl(0,n-1,0,n-1);
return 0;
}
//AC第一百题，不要问我为什么是道水题，希望这次能用脑子，距离day1结束不到24小时

var i,j,k:longint;

　　s1,s2:string;

procedure doit(zh,ho:string);

var le1,ri1,le2,ri2:string;

　　k:integer;

begin

　　k:=pos(ho[length(ho)],zh);

　　if(k=0) then exit;

　　write(zh[k]);

　　le1:=copy(zh,1,k-1);

　　le2:=copy(ho,1,k-1);

　　doit(le1,le2);

　　ri1:=copy(zh,k+1,length(zh)-k);

　　ri2:=copy(ho,k,length(ho)-k);

　　doit(ri1,ri2);

end;

begin

readln(s1);

readln(s2);

doit(s1,s2);

end.

递归；给定一个后续遍历和中序遍历，可以从后续遍历最后一个元素找到当前树的根节点，而在中序遍历中根节点处在左子树和右子树之间。由此可以找到左右子树分别的中、后序遍历，他们和一颗独立的二叉树没有区别，继续做同一个操作，就可以递归辣。

经验教训，
1. 差点忘了substr的参数，一个是pos,另一个是len。。。
2. 用了一下string.back()，然后用到后面不知道为什么存字符的char就空了。。。看了下介绍貌似是传的引用？（不用就是了，告辞）

代码

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

string inorder, postorder; //inorder, postorder

const int MAXN = 20;

int cnt;

struct tree{
    char node;
    int l, r;
} t[MAXN];

int dfs(string io, string po) {
    // cout << io << " " << po << endl;
    if (io.empty() || po.empty()) return 0;
    int curr = ++cnt;
    t[curr].node = po[po.length() - 1];
    po.pop_back();
    if (io.length() == 1) return curr;
    // cout << t[curr].node << endl;
    int mid = io.find(t[curr].node);
    // child reconstruction
    t[curr].l = dfs(io.substr(0, mid), po.substr(0, mid));
    t[curr].r = dfs(io.substr(mid + 1, string::npos), po.substr(mid, string::npos));
    return curr;
}

void print(int curr) {
    if (!curr) return;
    cout << t[curr].node;
    print(t[curr].l);
    print(t[curr].r);
}

int main() {
    cin >> inorder >> postorder;
    dfs(inorder, postorder);
    print(1); cout << endl;
    return 0;
}

python 递归

class node:
    def __init__(self, char):
        self.char = char
        self.left = None 
        self.right = None 

def build_tree(mid_seq, post_seq):
    if not mid_seq:
        return None
    
    root = post_seq[-1]
    new_node = node(root)
    root_pos_in_mid = mid_seq.find(root)

    new_node.left = build_tree(mid_seq[:root_pos_in_mid], post_seq[:root_pos_in_mid])
    new_node.right = build_tree(mid_seq[root_pos_in_mid+1:], post_seq[root_pos_in_mid:-1])
    return new_node

def generate_pre_seq(tree):
    if not tree:
        return ''
    return tree.char + generate_pre_seq(tree.left) + generate_pre_seq(tree.right)

mid_seq = input().strip()
post_seq = input().strip()
tree = build_tree(mid_seq, post_seq)
print(generate_pre_seq(tree))

#include <iostream>     //[2001普及组-C]求先序排列
#include <algorithm>
#include <string>
using namespace std;

void Fro(string mid, string lat, int len)
{
    if(len == 0)
        return;
    char A = lat[lat.length() - 1];
    cout << A;
    int k = mid.find(A);
    if(k >= 0)
    {
        Fro(mid.substr(0, k), lat.substr(0, k), k);
        Fro(mid.substr(k + 1, len - k - 1), lat.substr(k, len - k - 1), len - k - 1);
    }
}

int main()
{
    string mid, lat;
    cin >> mid >> lat;
    Fro(mid, lat, mid.length());

    return 0;
}

#include<stdio.h>
#include<string.h>
#include<queue>
std::queue<char>k;
char s1[30],s2[30];
int f2(char* s,char q,int len,char c);
int f1(char s,char q,int len)
{
if(len<1)return 0;
char c=s[len-1];
k.push(c);//将后序中最后一个元素压入，即当前子树的根节点。
if(len==1){
return 0;
}
else{
int index=f2(s,q,len,c);
f1(s,q,index);
f1(s+index,q+index+1,len-index-1);
return 0;
}
}
int f2(char s,char*q,int len,char c)
{
for(int i=0;i<len;i++)
{
if (q[i]==c)
return i;
}
}
int main()
{

scanf("%s",s1);
scanf("%s",s2);
int length=strlen(s2);
f1(s2,s1,length);//
for(int i=0;i<length;i++)
{
char t=k.front();
printf("%c",t);
k.pop();
}
return 0;
}

···
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
string ecs(string a,string b)
{
string jg;
int l,n=b.size();//n：后序序列总长
jg+=b[n-1];//取根节点，为先序序列第一个
l=a.find(jg[0]);//l：左子树长度
if(l>0)//就是判断有没有左子树、（先左后右）
jg+=ecs(a.substr(0,l),b.substr(0,l)); //取左子树，可以看作一个新的二叉树
if(l<n-1)//就是判断有没有右子树
jg+=ecs(a.substr(l+1,n-1-l),b.substr(l,n-1-l));
//同理取右子树，也可以看作一个新的二叉树
return jg;
}
int main()
{
string z,h;
cin>>z>>h;
cout<<ecs(z,h);
}
···

#include <bits/stdc++.h>
using namespace std;
char a[10],b[10];
void dfs(int l1,int r1,int l2,int r2){
if(l1>r1)return;
cout<<b[r2];
int i;
for(i=l1;i<=r1;i++){
if(a[i]==b[r2]){
break;
}
}
dfs(l1,i-1,l2,i-1-l1+l2);
dfs(i+1,r1,i-l1+l2,r2-1);
}
int main(){
scanf("%s%s",a,b);
dfs(0,strlen(a)-1,0,strlen(a)-1);
return 0;
}

#include<iostream>

#include<cstdio>

#include<string>

using namespace std;

string x,y;

void write(int p,int q,int m,int n)

{

if(p>q)return;

if(p==q){cout<<x[p];return;}

int i,j,k;

k=x.find(y[n]);

cout<<y[n];
write(p,k-1,m,m+k-p-1);
write(k+1,q,m+k-p,n-1);
}
int main()
{
int i,j,k;
cin>>x>>y;

k=x.length();

write(0,k-1,0,k-1);

return 0;

}

Var
        z,h,x:string;

Procedure dfs(z,h:string);
Var
        max,k,i:longint;
Begin
        if length(z)=0 then
                exit;
        max:=0;
        for i:=1 to length(z) do
                if pos(z[i],h)>max then
                begin
                        max:=pos(z[i],h);
                        k:=i;
                end;
        x:=x+z[k];
        if length(z)>1 then
        begin
                dfs(copy(z,1,k-1),h);
                dfs(copy(z,k+1,length(z)),h);
        end;
End;

Begin
        readln(z);
        readln(h);
        dfs(z,h);
        writeln(x);
        readln;
End.

恩。。超水的。恩。如果今年的第三题也这样就好了。。。

//有点简单粗暴，不过还是能过的
//参考http://blog.csdn.net/yuyanggo/article/details/47955809
#include <bits/stdc++.h>
 using namespace std;
 void write(string x, string y, char ch)
 {
    if(x.size() == 0 || y.size() == 0) return ;
    cout << ch;
    int index = x.find(ch);
    string x1 = x.substr(0, index);
    string x2 = x.substr(index + 1);
    string y1 = y.substr(0, x1.size());
    string y2 = y.substr(x1.size(), x2.size());
    write(x1, y1, y1[y1.size() - 1]);
    write(x2, y2, y2[y2.size() - 1]);
 }

 int main()
 {
    string x, y;
    cin >> x >> y;
    write(x, y, y[y.size() - 1]);
    return 0;
 }

#include"iostream"
#include"string"
#include"cstring"
#include"algorithm"
#include"cstdio"
using namespace std;
struct node{
node *lchild,*rchild;
char val;
};
string f(string a,int b,int e) //截取子串 STL 里面貌似有个函数但是记不到了。。。
{
string k="";
for(int i=b;i<=e;i++)
k+=a[i];
return k;
}

int n,n1;

node* build(string s1,string s2)
{

node root=(node)malloc(sizeof(node)); //先构造根节点
root->val=s2[s2.size()-1]; //后序遍历的最后一个字母就是根节点的值
root->lchild=root->rchild=NULL; //把左右儿子置为空

int pos=s1.find(root->val);
if(pos-0) //当先序遍历的根的 左边还有字母说明左子树不为空那个继续构造
{
string lefts1=f(s1,0,pos-1);
string lefts2=f(s2,0,pos-1);
root->lchild=build(lefts1,lefts2);
}
if(s1.size()-1-pos) //当先序遍历的根 的右边还有字母说明右子树不为空继续构造
{
string rights1=f(s1,pos+1,s1.size()-1);
string rights2=f(s2,pos,pos+rights1.size()-1);
root->rchild=build(rights1,rights2);
}
return root;
}
void in(node *root)
{
if(root)
{
printf("%c",root->val);
in(root->lchild);
in(root->rchild);
}
}
int main()
{
string s1,s2;
while(cin>>s1>>s2)
{
node *root=build(s1,s2);;
in(root);
printf("\n");
}
return 0;
}

人生苦短，我用python
```python
def build_tree(str1, str2):
if (str1 != "" and str2 != ""):
cha = str2[-1:]
i = str1.find(cha)
return cha+build_tree(str1[:i], str2[:i])+build_tree(str1[i+1:], str2[i:-1])
else:
return ""

print build_tree(raw_input(), raw_input())
```

通过中序遍历递归左右子树
不过要注意全是左子树或全是右子树的情况
       就因为这个被坑了快半小时ค(TㅅT)
program binary_tree;
var s1,s2:string;

procedure f(a,b:string);
var t:char;
i,c:longint;
begin
  if length(a)=1 then begin write(a);exit;end;
  if length(a)=2 then begin write(b[2],b[1]);exit;end;
  t:=b[length(b)];
  for i:=1 to length(a) do if t=a[i] then begin write(t);c:=i;break;end;
  if not(t=a[1]) then
    f(copy(a,1,c-1),copy(b,1,c-1));
  if t=a[length(a)] then exit;
  f(copy(a,c+1,length(a)-c),copy(b,c,length(b)-c));
end;

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

、、、pascal
program binary_tree;
var s1,s2:string;

procedure f(a,b:string);
var t:char;
i,c:longint;
begin
if length(a)=1 then begin write(a);exit;end;
if length(a)=2 then begin write(b[2],b[1]);exit;end;
t:=b[length(b)];
for i:=1 to length(a) do if t=a[i] then begin write(t);c:=i;break;end;
if not(t=a[1]) then
f(copy(a,1,c-1),copy(b,1,c-1));
if t=a[length(a)] then exit;
f(copy(a,c+1,length(a)-c),copy(b,c,length(b)-c));
end;

begin
readln(s1);
readln(s2);
f(s1,s2);
end.
、、、