Skip to main content

4279.笛卡尔树

caution

原题链接：https://www.acwing.com/problem/content/description/4282/

思路​

主要分为两个步骤：

  1. 建树

    因为题目说到这棵树满足堆的性质，并且是一个小根堆，所以所有子树的根节点都是最小值。并且题目给出输入的序列是一个中序遍历。

    所以我们只需要在这一个序列当中进行二分递归，找到区间当中最小值，然后以这个最小值的位置开始二分，递归构建出整棵树。

  2. 遍历

    直接用 bfs 即可。注意判断左节点或者右节点不空（此处用 -1 表示）的时候才可以加入到队列。

代码​

#include <bits/stdc++.h>

using namespace std;

const int N = 40;

struct Node {
    int l, r, w;
} tree[N];

queue<int> q;

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

int dfs(int l, int r) {
    if (l > r)
        return -1;
    // 找到每个子树的根节点，根节点都是那个区间里面最小的数
    // 因为输入序列是树的中序遍历，所以可以这样干，而且满足小根堆的性质
    int root = getmin(l, r);
    tree[root].l = dfs(l, root - 1);  // 找树的左子树
    tree[root].r = dfs(root + 1, r);  // 找树的右子树

    return root; // 返回每一个子树的根节点
}

void bfs(int root) {
    q.push(root);  // 从根开始一层层遍历

    while (!q.empty()) {
        int t = q.front();  // 取到根节点 t

        q.pop();  // 弹 出
        cout << tree[t].w << " ";  // 输 出

        if (tree[t].l != -1)
            q.push(tree[t].l);  // 看这个节点 t 的左边还有没有节点，遍历下一层
        if (tree[t].r != -1)
            q.push(tree[t].r);  // 看这个节点 t 的右边还有没有节点，遍历下一层
    }
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> tree[i].w;

    // 建树
    int root = dfs(0, n - 1);
    // bfs 层序遍历
    bfs(root);

    return 0;
}