文章
1
粉丝
182
获赞
1
访问
5.5k
# include <iostream>
# include <algorithm>
# include <unordered_map>
using namespace std;
string pre, ino;
unordered_map<int, int> mi;
int pos_idx; // 前序遍历目前访问的位置
// [ii, ij]: 中序遍历目前访问的区间
void dfs(int ii, int ij) {
if (ii > ij) return;
char val = pre[pos_idx];
int root_in_ino = mi[val];
pos_idx ++ ;
dfs(ii, root_in_ino - 1); // 遍历左子树
dfs(root_in_ino + 1, ij); // 遍历右子树
cout << val; // 访问根节点
return ;
}
int main() {
cin >> pre >> ino;
for (int i = 0; i < ino.size(); i ++ ) mi[ino[i]] = i;
dfs(0, ino.size() - 1);
return 0;
}
登录后发布评论