UVa 10821 Constructing BST

想法：
    在最上層的時候，假設我們有數列{1,2,3,4,5,6,7}，要選出一個數字當作該層的root，例如選擇'4'，那麼{1,2,3}就被分配到左子樹，{4,5,6}到右子樹，到下一層我們一樣從{1,2,3}和{4,5,6}選出各自的root，然後繼續到下一層。
    但題目有說輸出要盡可能小，所以選擇root的時候，要盡可能選靠左邊的數字，所以要讓右子樹填滿，例如現在最上層數列為{1,2,3,4,5,6}，深度H=3，代表子樹深還有2，則左右子樹各別能提供(2^2-1=3)3個空間，因此我們選擇'3'當作root，分成{1,2}和{4,5,6}到左右子樹，讓右子樹3個空間被填滿，一直遞迴下去直到分配完全部數字。

	#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);
	}

view raw [UVa] 10821 Constructing BST.cpp hosted with ❤ by GitHub