2023.12.15

#include <iostream>
#include <vector>

using namespace std;

vector<int> constructBinarySearchTree(int n, int k) {
    vector<int> permutation;

    if (k > log2(n+1)) { // 如果k大于树的最大高度，则无解
        return permutation;
    }

    // 将根节点添加到排列
    permutation.push_back(k+1);

    int left = 1; // 左子树的起始位置
    int right = n; // 右子树的起始位置

    // 从高度k开始构造树
    for (int i = k; i >= 1; i--) {
        if (i % 2 == 1) { // 如果当前高度是奇数，则将节点插入到左侧
            permutation.push_back(left);
            left++;
        } else { // 如果当前高度是偶数，则将节点插入到右侧
            permutation.push_back(right);
            right--;
        }
    }

    // 添加剩余的节点
    for (int i = n; i > k+1; i--) {
        permutation.push_back(i);
    }

    return permutation;
}

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

    vector<int> permutation = constructBinarySearchTree(n, k);

    if (permutation.size() == 0) {
        cout << "impossible" << endl;
    } else {
        for (int i = 0; i < permutation.size(); i++) {
            cout << permutation[i] << " ";
        }
        cout << endl;
    }

    return 0;
}

给定整数n和k，如果存在一个由1到n的排列，当按照这个顺序插入到一个空的二叉搜索树中时，生成的树的高度为k，则输出这个排列，否则输出"impossible"。

这个问题可以通过一种规律来解决。首先，我们将根节点放在排列的第k+1个位置。然后，我们从高度k开始构造树，每次交替将节点插入到左侧或右侧。最后，我们将剩余的节点按照降序插入到排列中。

如果k大于树的最大高度(log2(n+1))，则无解。否则，我们可以通过上述方法构造树，并输出排列。

需要注意的是，这个问题可能有多个解决方案，其中的任何一个都将被接受。