首页 > 代码库 > 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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。