A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
• Both the left and right subtrees must also be binary search trees.

A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.

Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer?N?(≤). Then?N?distinct non-negative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input:

10
1 2 3 4 5 6 7 8 9 0

Sample Output:

6 3 8 1 5 7 9 0 2 4

?

通過觀察可以注意到，對完全二叉樹當中的任何一個結點（設編號為x），其左孩子的編號一定是2x，而右孩子的編號一定是2x 1。也就是說，完全二叉樹可以通過建立一個大小為2k的數(shù)組來存放所有結點的信息，其中k為完全二叉樹的最大高度，且1號位存放的必須是根結點（想一想為什么根結點不能存在下標為0處？）。這樣就可以用數(shù)組的下標來表圖95完全二又樹編號示意示結點編號，且左孩子和右孩子的編號都可以直接計算得到。
事實上，如果不是完全二叉樹，也可以視其為完全二叉樹，即把空結點也進行實際的編號工作。但是這樣做會使整棵樹是一條鏈時的空間消耗巨大（對k個結點就需要大小為2^k的數(shù)組），因此很少采用這種方法來存放一般性質的樹。不過如果題目中已經規(guī)定是完全二叉樹，那么數(shù)組大小只需要設為結點上限個數(shù)加1即可，這將會大大節(jié)省編碼復雜度。
除此之外，該數(shù)組中元素存放的順序恰好為該完全二叉樹的層序遍歷序列。而判斷某個結點是否為葉結點的標志為：該結點（記下標為root）的左子結點的編號root * 2大于結點總個數(shù)n（想一想為什么不需要判斷右子結點？）；判斷某個結點是否為空結點的標志為：該結點下標 root大于結點總個數(shù)n。

?

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 int N, nums[1001], res[1001], index = 0;
 6 void levelOrder(int k)
 7 {
 8     if (k > N)//葉子節(jié)點
 9         return;
10     levelOrder(k * 2);//遍歷左子樹
11     res[k] = nums[index  ];//即遍歷完左子樹后，此時即為根節(jié)點
12     levelOrder(k * 2   1);//遍歷右子樹
13 }
14 int main()
15 {
16     cin >> N;
17     for (int i = 0; i < N;   i)
18         cin >> nums[i];
19     sort(nums, nums   N, [](int a, int b) {return a < b; });
20     levelOrder(1);
21     for (int i = 1; i <= N;   i)
22         cout << res[i] << (i == N ? "" : " ");
23     return 0;
24 }

?