首先先来复习一下递归法解决问题。引例就用十分经典的汉诺塔问题。
先用数学归纳法，算出n个盘子所需要的最少步骤为2^n-1次。（动态规划的数学基础是数学归纳法，此处的递归也有某种通性）
递归时要考虑最基础的步骤，那就是分三步。
第一步，将上面的n-1个盘子从A移到B
第二步，将第n个盘子从A移到C
第三部，将那n-1个盘子从B移到C
所以可以写出递归函数
//a 起始 b 临时 c 终点 注意 此abc非彼ABC
void move(int t,char a,char b,char c)
{
if(t==1)//只有1个时要单独判断
printf("%d from %c to %c\n",t,a,c);
else
{
move(t-1,a,c,b);//先把t-1放到临时
printf("%d from %c to %c\n",t,a,c);//从起始到终点
move(t-1,b,a,c);//把t-1取回，放到终点
}
}
接着我们来看看遍历二叉树的最基础的四个方式
1.BFS 层序遍历 (宽度优先遍历)
此时用到的方法是利用队列收集并排序所要输出的节点。
int bfs()
{
queue<int> q;
q.push(root);//首先要把根节点push进
int i=0;//用来向ans中加入输出队列
while(!q.empty())//当队列非空时
{
int t=q.front();//先把队首元素保存起来
q.pop();//把front存起来之后即可抛弃
if(nodes[t]==0) return 0;//失败
ans[i++]=nodes[t];//存入队首元素
if(left[t])//当前节点有左儿子
q.push(left[t]);//存入
if(right[t])//当前节点有右儿子
q.push(right[t]);//存入
}
return 1;
}
//宽度优先遍历bfs int bfs(){cnt=0;queue<Node*> q;q.push(root);while(!q.empty()){Node* u = q.front();q.pop();if(!u->hv) return 0;//没有被赋值 ans[cnt++]=u->v; if(u->l!=NULL) q.push(u->l); if(u->r!=NULL) q.push(u->r);}return 1;}
2.前序 中序 后序 （均用递归实现，代码类似）
void PreOrder(int node)最后三行代码的顺序决定了输出节点的时机，不同的递归结果使得最后的遍历效果分别不同。
{
if(node==0)//到了尽头
return;
cout<<node<<" ";
PreOrder(l[node]);
PreOrder(r[node]);
}
重点来了，那就是根据前序和中序 确定后序的结果
例如 DBACEFG ABCDEFG 输出 ACBFGED
此时的递归较为难以理解
char s1[255],s2[255],ans[255];暂时的递归就理解到如此吧，相信以后的学习会更加深入地理解的
//s1是当前的前序 s2是中序 s是用于当前树的后序存储
void build(int n,char* s1,char* s2,char* s)
{
if(n<=0)return; //p=0时 说明已到达左终点 n-p-1<=0是说明已到达右终点
//用p记录根节点在中序遍历中的位置(0是第一位) 此时p也同时表示了左子树的节点数
//n-1-p是右子树的节点数
int p=strchr(s2,s1[0])-s2; //s2是s2[0]的指针地址
//对前p个元素（上一节点的左子树）进行后序遍历重建
build(p,s1+1,s2,s) ; //因为参数n是p所以不会打扰右字数的排列 到了尽头就返回
//对后n-1-p个元素（上一节点的右子树进行后序遍历重排）
build(n-1-p,s1+p+1,s2+p+1,s+p); //s+p因为前p个元素是左子树写过了的
s[n-1]=s1[0]; //把每个树的根节点写到后序遍历的最后一个位置
}
int main()
{
cin>>s1>>s2;
int n=strlen(s1);
build(n,s1,s2,ans);
ans[n]='\0';
cout<<ans;
}