[jobdu] 두 갈래 나무의 거울

#include <iostream>

#include <vector>

using namespace std;



void preOrder(vector<vector<int> > &tree, vector<int> &val, vector<int> &ans, int root) {

    if (root == -1) return;

    else {

        ans.push_back(val[root]);

        preOrder(tree, val, ans, tree[root][1]);

        preOrder(tree, val, ans, tree[root][0]);

    }

}



int main() {

    int n;

    while (cin >> n)

    {

        vector<vector<int> > tree(n+1);

        vector<int> val(n+1);

        for (int i = 1; i <= n; i++) {

            int tmp;

            cin >> tmp;

            val[i] = tmp;

        }

        for (int i = 1; i <= n; i++) {

            char type;

            cin >> type;

            if (type == 'd') {

                int x, y;

                cin >> x >> y;

                tree[i].push_back(x);

                tree[i].push_back(y);

            }

            else if (type == 'l') {

                int x;

                cin >> x;

                tree[i].push_back(x);

                tree[i].push_back(-1);

            }

            else if (type == 'r') {

                int x;

                cin >> x;

                tree[i].push_back(-1);

                tree[i].push_back(x);

            }

            else if (type == 'z') {

                tree[i].push_back(-1);

                tree[i].push_back(-1);

            }

        }

        if (n == 0) {

            cout << "NULL" << endl;

            continue;

        }

        vector<int> ans;

        preOrder(tree, val, ans, 1);

        for (int i = 0; i < ans.size() - 1; i++) {

            cout << ans[i] << " ";

        }

        cout << ans[ans.size()-1] << endl;

    }

}