AcWing 1497. 树的遍历
原题链接
简单
作者:
麦克斯韦妖_7
,
2021-08-22 16:53:32
,
所有人可见
,
阅读 183
#include <iostream>
#include <queue>
using namespace std;
struct node{
int val;
node* left = NULL;
node* right = NULL;
};
int post[40], in[40];
node* create(int postL, int postR, int inL, int inR){
if(postL > postR) return NULL;
node* root = new node;
root->val = post[postR];
int k;
for(k = inL; k <= inR; k ++){
if(in[k] == post[postR]) break;
}
int numLeft = k - inL;
root->left = create(postL, postL + numLeft - 1, inL, k - 1);
root->right = create(postL + numLeft, postR - 1, k + 1, inR);
return root;
}
void BFS(node* root){
queue<node*> q;
q.push(root);
while(!q.empty()){
node* cur = q.front();
q.pop();
cout << cur->val << ' ';
if(cur->left != NULL) q.push(cur->left);
if(cur->right != NULL) q.push(cur->right);
}
}
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i ++) cin >> post[i];
for(int i = 0; i < n; i ++) cin >> in[i];
node* root = create(0, n - 1, 0, n - 1); // 建树
BFS(root); // 遍历
return 0;
}