我的递归思维一直很差，潜意识里总是觉得这种思维不是真正的解决问题，所以，总是想用递推思维思考问题。
给定二叉树的前序和中序，输出后序是数据结构中的基本问题，我一直不敢上机实践，就怕自己做不出来。恰好今晚有两个战友，无聊之极，试一试，果断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("");
}
}