4279. 笛卡尔树

思路：dfs小根堆建树，记录每一层的节点

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 40;


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()
{
    
    int n;
    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;
}

思路： 模拟建树，bfs

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 40;


int w[N];
int q[N];
int L[N], R[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;
}

int dfs(int l, int r){
    
    
    if(l > r) return -1;
    
    int root = getmin(l,r);
    
    L[root] = dfs(l, root - 1);
    R[root] = dfs(root + 1, r);
    
    return root;
    
}

void bfs(int root){
    
    int hh = 0, tt = 0;
    
    q[0] = root;
    while(hh <= tt){
    
        int x = q[hh++];
        cout << w[x] << ' ';
        if(L[x] != -1) q[++tt] = L[x];
        if(R[x] != -1) q[++tt] = R[x];
    }
    
    
}
int main()
{
    
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i++)
        cin >> w[i];
        
    int root = dfs(0, n-1);
    
    bfs(root);
    
    
    return 0;
}