AcWing 3598. 二叉树遍历
原题链接
简单
作者:
在下木子
,
2024-04-14 00:00:53
,
所有人可见
,
阅读 5
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
const int N = 1001;
char a[N];//存储前序
char b[N];//存储中序
unordered_map<char,int> p;
vector<char> arr;
void solve(int al,int ar,int bl,int br)
{
if(al > ar) return;
char root = a[al];
int k = p[root];
solve(al+1,k-bl+al,bl,k-1);//遍历左子树
solve(k-bl+al+1,ar,k+1,br);//遍历右子树
arr.push_back(root);
}
int main()
{
string n,m;
while(cin>>n>>m){
for(int i = 0;i<n.length();i++){
a[i] = n[i];
}
for(int j = 0;j<m.length();j++){
b[j] = m[j];
p[b[j]] = j;
}
arr.clear();
solve(0,n.length()-1,0,m.length()-1);
for(int z = 0;z<arr.size();z++)
{
cout<<arr[z];
}
cout<<endl;
}
}