Untitled

mail@pastecode.io avatar
unknown
c_cpp
a month ago
1.4 kB
3
Indexable
Never
#include <iostream>
#include <vector>
#include <functional>
using namespace std;

struct node
{
    int val;
    node *l = NULL;
    node *r = NULL;
    node(int x, node *l = NULL, node *r = NULL) : val(x) {}
};

int main()
{
    int t;
    cin >> t;
    for (int j = 0; j < t; j++)
    {
        int n;
        cin >> n;
        vector<int> pre(n + 5), in(n + 5), pos(n + 5), post(n + 5);
        for (int i = 0; i < n; ++i)
            cin >> pre[i];
        for (int i = 0; i < n; ++i)
        {
            cin >> in[i];
            pos[in[i]] = i;
        }
        for (int i = 0; i < n; ++i)
            cin >> post[i];

        function<node *(int, int)> build = [&](int l, int r)
        {
            if (l > r)
                return (node *)(NULL);
            static int now = 0;
            node *res = new node(pre[now++]);
            res->l = build(l, pos[res->val] - 1);
            res->r = build(pos[res->val] + 1, r);
            return res;
        };

        function<void(node *)> postorder = [&](node *t)
        {
            if (!t)
                return;
            postorder(t->l);
            postorder(t->r);
            cout << t->val << ' ';
            return;
        };

        node *x = build(0, n - 1);
        postorder(x);
        cout << "\n";
    }
}
Leave a Comment