[UVa] 10821 Constructing BST.cpp

#include <cstdio>
#include <cmath>
using namespace std;
void BST(int Left, int Right, int H);
int main()
{
    int Case = 1;
    int N, H;
    while (scanf("%d %d", &N, &H) && (N || H)) {
        printf("Case %d:", Case++);
        if (pow(2,H) - 1 < N) {
            puts(" Impossible.");
            continue;
        }
        if (H > N) H = N; // 深度如果大於總數就讓H=N
        BST(1, N, H);
        putchar('\n');
    }
}
void BST(int Left, int Right, int H)
{
    if (H == 0 || Left > Right) return;
    //下一個root應盡可能靠左,所以把右子樹填滿
    int right_space = pow(2, H - 1) - 1; //右子樹空間
    int root = Right - right_space;
    if (root < Left) root = Left;

    printf(" %d", root);

    BST(Left, root - 1, H - 1);
    BST(root + 1, Right, H - 1);
}