AcWing 1631. 后序遍历(哈希表优化)
原题链接
简单
作者:
麦克斯韦妖_7
,
2021-08-27 23:19:57
,
所有人可见
,
阅读 585
/*用哈希表优化建树过程*/
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
struct node{
int data;
node *left, *right;
};
int pre[50010], in[50010];
vector<int> v;
unordered_map<int, int> m;
node* create(int preL, int preR, int inL, int inR){
if(preL > preR) return NULL;
node* root = new node;
root->data = pre[preL];
int k = m[pre[preL]];
// for(k = inL; k <= inR; k ++) /*改为哈希表*/
// if(in[k] == pre[preL]) break;
int numLeft = k - inL;
root->left = create(preL + 1, preL + numLeft, inL, k - 1);
root->right = create(preL + numLeft + 1, preR, k + 1, inR);
return root;
}
void post(node* root){
if(root == NULL) return;
post(root->left);
post(root->right);
v.push_back(root->data);
}
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i ++) cin >> pre[i];
for(int i = 0; i < n; i ++){
cin >> in[i];
m[in[i]] = i;
}
node* root = create(0, n - 1, 0, n - 1);
post(root);
cout << v[0];
return 0;
}