题意
输入一棵二叉树的先序遍历和中序遍历序列，输出它的后序遍历序列。
输入
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个字符.如果第二个参数不写,默认截取到最后.
