题意
输入一棵二叉树的先序遍历和中序遍历序列,输出它的后序遍历序列。
输入
DBACEGF ABCDEFG
BCAD CBAD
输出
ACBFGED
CDAB
思路:我们可以通过二叉树的先序和中序可以推出后序节点.先序得根,中序分左右,通过递归便可输出后序节点.
此题中只是输出后序,没有必要存储起来.
#include<bits/stdc++.h>
using namespace std;
string preorder,inorder;
void solve(string pre,string in){
int index = in.find(pre[0]);
if(pre==""){//递归结束条件
return;
}
solve(pre.substr(1,index),in.substr(0,index)) ;
solve(pre.substr(index+1),in.substr(index+1));
cout<<pre[0];
}
int main()
{
while(cin>>preorder>>inorder){
solve(preorder,inorder);
cout<<endl;
}
return 0;
}
由于上面是参数传递的是字符串,中间用到了substr函数,在处理时效率较低,所以我们可以把参数改为传递索引,这样效率就大大提高了.
参考代码2
#include<bits/stdc++.h>
using namespace std;
string preorder,inorder;
void solve(int pre,int in,int len){
if(len <= 0){//结束条件
return;
}
int index = inorder.find(preorder[pre])-in;//根节点在中序的位置索引 -- 字符串起始索引就是根节点左右子树的结点数.
solve(pre+1,in,index);
solve(pre+index+1,in+index+1,len-index-1);//左右子树的节点数不一定相等,所以得用总长度-左子树结点的个数 要注意索引是从0开始的.所以最后要-1
cout<<preorder[pre];
}
int main()
{
while(cin>>preorder>>inorder){
int len = preorder.size();
solve(0,0,len);//分别指代 先序起始索引,中序起始索引, 长度
cout<<endl;
}
return 0;
}
注:substr(index,pos),从index开始截取pos个字符.如果第二个参数不写,默认截取到最后.