Learning4Fun ural 1210

/* 题意：给出一颗二叉树的中序遍历和后序遍历，求出其右左中的遍历
 * 解法：一边根据已知的两种序列进行树的dfs同时打印出要求遍历的序列。
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <cstdio>
using namespace std;
#define vN 30003
int base[2][3005];
stack<int> T;
int n;
int dfs(int root, int pos, int s, int e)
{
    if (T.size() == 0)
    {
        cout << root << " ";
        return 0;
    }
    int u = T.top();
    for (int i = pos + 1; i <= e; i++)
    {
        if (base[1][i] == u)
        {
            T.pop();
            dfs(u, i, pos + 1, e);
        }
    }
    if (T.size() == 0)
    {
        cout << root << " ";
        return 0;
    }
    u = T.top();
    for (int i = s; i < pos; i++)
    {
        if (base[1][i] == u)
        {
            T.pop();
            dfs(u, i, s, pos - 1);
        }
    }
    cout << root << " ";
    return 0;
}
int main()
{
    //freopen("data.in", "r", stdin);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> base[0][i];
        T.push(base[0][i]);
        base[1][i] = base[0][i];
    }
    sort(base[1], base[1] + n);
    int u = T.top();
    T.pop();
    int pos;
    for (int i = 0; i < n; i++)
    {
        if (base[1][i] == u)
            pos = i;
    }
    dfs(u, pos, 0, n - 1);
    return 0;
}