BST: binary search tree.
题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1762
题目中要求构造的BST的高度最多为H，也就是说可以比H小（之前没注意到这点）。如果有若干顺序满足高度为H的BST，取小数字排在前面的顺序，所以在构造BST的过程中，尽可能使right sub-tree填满。数字排在right sub-tree最多可以有pow(2, height-1)个，所以当前root是max（left, right-pow(2, height-1)）。递归解决所有的sub-tree。
代码如下：
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <queue>
#include <vector>
#include <functional>
#include <cmath>
#define SCF(a) scanf("%d", &a)
#define IN(a) cin>>a
#define FOR(i, a, b) for(int i=a;i<b;i++)
typedef long long Int;
using namespace std; void order(int start, int end, int height)
{
if (start > end)
return;
if (height == 0)
printf(" %d", start);
else
{
int n = pow(2, height - 1) - 1;
int num = end - start + 1;
if (num > n)
{
int root = end - n;
printf(" %d", root);
order(start, root - 1, height - 1);
order(root + 1, end, height - 1);
}
else
{
printf(" %d", start);
order(start+1, end, height - 1);
}
} } int main()
{
int N, H;
int t = 1;
while (SCF(N) && SCF(H))
{
if (N == 0 && H == 0)
break;
if (H < floor(log2(N) + 1))
printf("Case %d: Impossible.\n", t++);
else
{
printf("Case %d:", t++);
if (H > N)
H = N;
order(1, N, H);
printf("\n");
}
}
return 0;
}