笛卡尔树（暑假每日一题 9）

笛卡尔树 是由一系列不同数字构成的二叉树。

树满足堆的性质，中序遍历返回原始序列。
最小笛卡尔树表示满足小根堆性质的笛卡尔树。

例如，给定序列 $\{8,15,3,4,1,5,12,10,18,6\}$，则生成的最小堆笛卡尔树如图所示。

现在，给定一个长度为 $N$ 的原始序列，请你生成最小堆笛卡尔树，并输出其层序遍历序列。

输入格式
第一行包含整数 $N$。

第二行包含 $N$ 个两两不同的整数，表示原始序列。

输出格式
共一行，输出最小堆笛卡尔树的层序遍历序列。

数据范围
$1\le N\le 30,$
原始序列中元素的取值范围 $[-2147483648,2147483647]$。

输入样例：

10
8 15 3 4 1 5 12 10 18 6

输出样例：

1 3 5 8 4 6 15 10 12 18

---

• 根据小根堆的性质，当前子树的根节点是当前区间元素中最小的，且中序遍历结果为原序列可以得出，根节点左边的元素是当前节点的左子树，右边的元素是当前节点的右子树。
• 递归实际上是一种前序遍历，所以可以将当前元素加入 层数为 d 的数组中，然后再依次遍历每层的数组，遍历结果为层序遍历结果。

不用 bfs

#include<iostream>
#include<vector>

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(int j = 0; j < level[i].size(); j++)
            cout << level[i][j] << ' ';
    
    return 0;
}

用bfs

#include<iostream>
#include<vector>

using namespace std;

const int N = 40;

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

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 u = q[hh ++];
        if(L[u] != -1) q[++tt] = L[u];
        if(R[u] != -1) q[++tt] = R[u];
    }
    
    for(int i = 0; i <= tt; i++)
        cout << w[q[i]] << ' ';
}

int main(){
    
    
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> w[i];
    
    int root = dfs(0, n - 1);
    bfs(root);
    
    return 0;
}