摘要
Title: 4279. 笛卡尔树
Tag: 笛卡尔树
Memory Limit: 64 MB
Time Limit: 1000 ms

4279. 笛卡尔树

题意

笛卡尔树是由一系列不同数字构成的二叉树。
树满足堆的性质，中序遍历返回原始序列。
最小笛卡尔树表示满足小根堆性质的笛卡尔树。
例如，给定序列 {8,15,3,4,1,5,12,10,18,6}，则生成的最小堆笛卡尔树如图所示。
现在，给定一个长度为 N 的原始序列，请你生成最小堆笛卡尔树，并输出其层序遍历序列。
思路

最小笛卡尔树：要求中序遍历为原数组，且满足最小堆的性质
- 所以找到数组的最小值作为根节点，左边的节点都在根节点的左子树上，右边的节点都在根节点的右子树上，递归这个过程即可构建笛卡尔树。
- 层次遍历也很容易实现，笛卡尔树本身就是从上到下，从左到右构建的，在构建过程中进行节点记录即可完成层次遍历输出。
- ps: 当然也可以单调栈线性建树

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-07-23 14:09:15
* @FilePath: \Acwing\4279\4279.cpp
* @LastEditTime: 2022-07-23 14:59:03
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;

const int INF = INT_MAX;
const int N = 1e6 + 10;

signed main()
{
    IOS;
    int n;
    cin >> n;
    vector<int> a(n), L(n), R(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    
    // 正常DFS建树
    function<int(int, int)> dfs = [&](int l, int r) {
        if (l > r)
            return -1LL;
        int root = min_element(a.begin() + l, a.begin() + r + 1) - a.begin();
        L[root] = dfs(l, root - 1);
        R[root] = dfs(root + 1, r);
        return root;
    };

    int root = dfs(0, n - 1);

    queue<int> q;
    q.push(root);
    while (SZ(q))
    {
        auto t = q.front();
        q.pop();
        cout << a[t] << " ";
        if (L[t] != -1)
            q.push(L[t]);
        if (R[t] != -1)
            q.push(R[t]);
    }
    return 0;
}

4279. 笛卡尔树

题意

思路

代码