首页 > 代码库 > uva 10821 - Constructing BST(BSF)

uva 10821 - Constructing BST(BSF)

题目链接:uva 10821 - Constructing BST

题目大意:给定节点个数以及树的高度,求一个字典序最小的插入顺序,使得生成的BST高度为H。

解题思路:根据H来确定说左右子树的节点个数,因为要求字典序尽量小,所以右子树的节点个数应该尽量多。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int N, H;

void solve (int l, int r, int h) {
    if (l > r)
        return;

    int mid = max(r - (1<<h) + 1, l);
    printf(" %d", mid);
    solve(l, mid - 1, h - 1);
    solve(mid + 1, r, h - 1);
}

int main () {
    int cas = 0;
    while (scanf("%d%d", &N, &H) == 2 && N + H) {
        printf("Case %d:", ++cas);
        if (N > (1<<H) - 1)
            printf(" Impossible.");
        else
            solve(1, N, H - 1);
        printf("\n");
    }
    return 0;
}

uva 10821 - Constructing BST(BSF)