Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<cstdio>
- #include<queue>
- using namespace std;
- const int MAXN = 30;
- struct Node{
- int data;
- Node* left;
- Node* right;
- };
- int post[MAXN];
- int in[MAXN];
- int n;
- Node* reconstruct(int post_left, int post_right, int in_left, int in_right){
- if(post_left>post_right) return NULL;
- Node* root = new Node;
- root->data = post[post_right];
- int k = in_left;
- for(;k<=in_right;k++){
- if(in[k]==post[post_right]) break;
- }
- int num = k-in_left;
- root->left = reconstruct(post_left, post_left+num-1, in_left, k-1);
- root->right = reconstruct(post_left+num, post_right-1, k+1, in_right);
- return root;
- }
- void layerOrder(Node* root){
- queue<Node*> q;
- q.push(root);
- int i=0;
- while(!q.empty()){
- Node* now = q.front();
- q.pop();
- i++;
- printf("%d", now->data);
- if(i<n) printf(" ");
- if(now->left!=NULL) q.push(now->left);
- if(now->right!=NULL) q.push(now->right);
- }
- printf("\n");
- }
- int main(){
- freopen("in.txt", "r", stdin);
- scanf("%d", &n);
- for(int i=0;i<n;i++) scanf("%d", &post[i]);
- for(int i=0;i<n;i++) scanf("%d", &in[i]);
- Node* root = reconstruct(0, n-1, 0, n-1);
- layerOrder(root);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement