40 lines
775 B
C++
40 lines
775 B
C++
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
void preOrder(string in,string post){
|
|
if(in.length() == 0) {
|
|
return;
|
|
}
|
|
char root=post[post.size()-1];
|
|
cout<<root; //输出根节点
|
|
int k=in.find(root);
|
|
|
|
//递归左右子树
|
|
preOrder(in.substr(0, k), post.substr(0, k));
|
|
preOrder(in.substr(k+1), post.substr(k, in.size()-k-1));
|
|
}
|
|
|
|
void postOrder(string pre, string in)
|
|
{
|
|
if (pre.length() == 0) {
|
|
return;
|
|
}
|
|
char root = pre[0];
|
|
int k = in.find(root);
|
|
//递归左右子树
|
|
postOrder(pre.substr(1, k), in.substr(0, k));
|
|
postOrder(pre.substr(k+1), in.substr(k+1));
|
|
putchar(root); //输出根节点
|
|
}
|
|
|
|
int main(){
|
|
ios::sync_with_stdio(false);
|
|
cin.tie(0);
|
|
|
|
string inOrder, postOrder;
|
|
cin>>inOrder>>postOrder;
|
|
preOrder(inOrder, postOrder);
|
|
cout<<endl;
|
|
return 0;
|
|
}
|