我的递归思维一直很差，潜意识里总是觉得这种思维不是真正的解决问题，所以，总是想用递推思维思考问题。

给定二叉树的前序和中序，输出后序是数据结构中的基本问题，我一直不敢上机实践，就怕自己做不出来。恰好今晚有两个战友，无聊之极，试一试，果断AC了，当然，这题poj的数据比较弱，我去了zoj，依然ac，估计水题没必要出强大数据吧。

期末要考《数据结构》这题给了我很大信心，真的！

很难想象，这是我poj的第206题，呵呵，今晚战胜了心魔，熬夜，值了！！！

贴一个poj上的递推代码，很漂亮。

#include <iostream>

#include <string>

using namespace std;

string f(string s1,string s2)

{

if(s1.length()==1) return s1;

else if(s1.length()==0) return "";

else

{

size_t m=s1.find(s2[0]);

return f(s1.substr(0,m),s2.substr(1,m))+f(s1.substr(m+1),s2.substr(m+1))+s2[0];

}

}

int main()

{

string s1,s2,s;//s1为preorder traversal  s2为inorder traversal 

while(cin>>s1>>s2)

{

s=f(s2,s1);

cout<<s<<endl;

}

return 0;

}

偷偷把我的代码放到最后，就不解释了吧。。。

/* 

 * File:   main.cpp

 * Author: lmm333

 * Created on 2010年12月16日

 */

#include <iostream>

#include <string>

using namespace std;

char a[30],b[30];

void f(int a1,int b1,int a2,int b2){

    int l,r,p2,i;

    char p1=a[a1];

    for(i=a2;i<=b2;i++){

        if(b[i]==p1)break;

    }

    l=i-a2;

    r=b2-i;

    if(l==0);

    else if(l==1)

        put("%c",b[a2]);

    else f(a1+1,i-1,a2,i-1);

    if(r==0);

    else if(r==1)

        put("%c",b[i+1]);

    else f(a1-a2+i+1,b1,i+1,b2);

    put("%c",b[i]);

}

int main(){

    int l;

    while(scanf("%s%s",a,b)!=EOF){

        l=strlen(a);

        f(0,l-1,0,l-1);

        puts("");

    }

}