pat 1020

1020.cpp

#include <cstdio>
#include <queue>

using namespace std;

struct node_t {
    node_t *left;
    node_t *right;
    int data;
};

int pos[50];
int ino[50];
int levo[50];

node_t *build_tree(int *pos_first, int *ino_first, int n) {
    node_t *node = NULL;

    if (n < 1) {
        return NULL;
    }

    int r_i = 0;
    while(ino_first[r_i] != pos_first[n-1]) {
        r_i++;
    }

    node = new node_t;
    node->data = pos_first[n-1];
    node->left = build_tree(pos_first, ino_first, r_i);
    node->right = build_tree(pos_first + r_i, ino_first + r_i + 1, n - r_i - 1);
    
    return node;
}

void level_travse(node_t *root, int *result) {
    queue<node_t *> que;
    que.push(root);
    while (!que.empty()) {
        node_t *node = que.front();
        que.pop();
        *result++ = node->data;
        if (node->left) {
            que.push(node->left);
        }
        if (node->right) {
            que.push(node->right);
        }
    }
}

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

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

    node_t *tree = build_tree(pos, ino, N);

    level_travse(tree, levo);

    printf("%d", levo[0]);
    for(int i = 1; i < N; i++) {
        printf(" %d", levo[i]);
    }
    puts("");

    return 0;
}