摘要
Title: A1064 Complete Binary Search Tree
Tag: 完全二叉树
Memory Limit: 64 MB
Time Limit: 1000 ms

A1064 Complete Binary Search Tree

题意

二叉搜索树 (BST) 递归定义为具有以下属性的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
它的左、右子树也分别为二叉搜索树
完全二叉树 (CBT) 定义为除最深层外的其他层的结点数都达到最大个数，最深层的所有结点都连续集中在最左边的二叉树。
现在，给定 N 个不同非负整数，表示 N 个结点的权值，用这 N 个结点可以构成唯一的完全二叉搜索树。
请你输出该完全二叉搜索树的层序遍历。
思路

完全二叉树可以用一维数组存，按中序遍历的顺序填进去即可

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-09-12 20:20:02
* @FilePath: \GPLT\A1064\A1064.cpp
* @LastEditTime: 2022-09-12 20:24:56
*/
#include <bits/stdc++.h>
using namespace std;
#define N n + 100
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

// #undef N
// const int N = 1e5 + 10;

// #undef int

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

    vector<int> w(n), tr(N);

    for (int i = 0; i < n; ++i)
        cin >> w[i];
    sort(w.begin(), w.end());

    int id = 0;
    function<void(int)> dfs = [&](int u) {
        if (u * 2 <= n)
            dfs(u * 2);
        tr[u] = w[id++];
        if (u * 2 + 1 <= n)
            dfs(u * 2 + 1);
    };

    dfs(1);

    cout << tr[1];
    for (int i = 2; i <= n; ++i)
    {
        cout << " " << tr[i];
    }

    return 0;
}

A1064 Complete Binary Search Tree

题意

思路

代码