题目描述
blablabla
样例
#include<iostream>
#include <algorithm>
#include <string>
#include <unordered_map>
using namespace std;
struct Node {
char val;
Node *left, *right;
Node(char _val): val(_val),left(NULL), right(NULL){}
};
string res;
void dfs(Node *root){
if(!root) return;
res += root->val;
dfs(root->left);
dfs(root->right);
}
int main(){
string inorder, lorder;
cin >> inorder >> lorder;
//获取中序的所有值
unordered_map<char, int> pos;
for(int i =0; i < inorder.size(); i++) pos[inorder[i]] = i;
bool st[30] = {0};
Node *q[30];
q[0] = new Node(lorder[0]);
for(int i =0, j = 1; j < lorder.size(); ){
for(int end = j; i < end; i++){ //按层遍历
int p = pos[lorder[i]];
//标记
st[p] = true;
//左边查
if(p && !st[p -1]){
//取值
q[i]->left = new Node(lorder[j]);
//还原
q[j++] = q[i]->left;
}
//右边查
if(p+1 < lorder.size()&& !st[p+1]){
q[i]->right = new Node(lorder[j]);
q[j++] = q[i]->right;
}
}
}
dfs(q[0]);
cout << res << endl;
return 0;
}