Untitled
raw download clone
C
views 27
,
size 1500 b
#include<stdio.h>
#include<stdlib.h>

typedef struct Stack{
    int* s;
    int top;
}stack;


stack* create(int n){
    stack* new = (stack*)malloc(sizeof(stack));
    new->top = -1;
    new->s = (int*)malloc(n*sizeof(int));
    return new;
}

void push(stack* a,int k){
    a->top ++;
    a->s[a->top] = k;
}

int pop(stack* a){
    int k = a->s[a->top--];
    return k;
}

void reconstruct(int* pre,int* in,stack* S,int len){
    if(len == 1)
    {   
        push(S,pre[0]);
        return;
    }

    int root = pre[0];

    push(S,root);

    int i;

    for (i = 0; i < len ; i++)
    {
        if (in[i] == root)
        {
            break;
        }
    }
    
    if((len-i-1) != 0)  reconstruct(pre+i+1,in+i+1,S,len-i-1);
    if(i != 0)  reconstruct(pre+1,in,S,i);
}

int main(int argc, char const *argv[])
{
    int n;

    scanf("%d",&n);

    int* in = (int*)malloc(n*sizeof(int)); 
    int* pre = (int*)malloc(n*sizeof(int));
    int* post = (int*)malloc(n*sizeof(int));  
    
    stack* S = create(n);

    for (int i = 0; i < n; i++)
    {
        scanf("%d",&pre[i]);
    }

    for (int i = 0; i < n; i++)
    {
        scanf("%d",&in[i]);
    }
    
    reconstruct(pre,in,S,n);

    for (int i = 0; i < n; i++)
    {
        if (i > 0)
        {
            printf(" ");
        }
        printf("%d",pop(S));
    }
    
    free(S->s);
    free(S);

    printf("\n");

    return 0;
}
close fullscreen
Login or Register to edit or fork this paste. It's free.