4279. Cartesian tree

Cartesian tree It is a binary tree composed of a series of different numbers .

The tree satisfies the nature of heap , Middle order traversal returns the original sequence .
The minimum Cartesian tree represents a Cartesian tree satisfying the property of small root heap .

for example , Given sequence {8,15,3,4,1,5,12,10,18,6}, The generated minimum heap Cartesian tree is shown in the figure .

Now? , Given a length of N The original sequence of , Please generate the minimum heap Cartesian tree , And output its sequence traversal sequence .

Input format

The first line contains integers N.

The second line contains N Two different integers , Represents the original sequence .

Output format

All in one line , Output the sequence traversal sequence of the minimum heap Cartesian tree .

Data range

1≤N≤30,
The value range of elements in the original sequence [−2147483648,2147483647][−2147483648,2147483647].

sample input ：

10
8 15 3 4 1 5 12 10 18 6

sample output ：

1 3 5 8 4 6 15 10 12 18

Code ：

#include <bits/stdc++.h>
using namespace std;

const int N = 40;

int n;
int w[N];
vector<int> level[N];

int getmin(int l, int r)
{
    
    int res = l;
    for (int i = l; i <= r; i++)
        if (w[res] > w[i])
            res = i;
    return res;
}

void dfs(int l, int r, int d)
{
    
    if (l > r)
        return;
    int root = getmin(l, r);
    level[d].push_back(w[root]);
    dfs(l, root - 1, d + 1);
    dfs(root + 1, r, d + 1);
}
int main()
{
    
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> w[i];

    dfs(0, n - 1, 0);
    for (int i = 0; level[i].size(); i++)
        for (auto x : level[i])
            cout << x << ' ';

    return 0;
}