1064 Complete Binary Search Tree

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.

p>

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N distinct non-negative integer keys are given in the next line. All the numbers in a line areseparated 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 theline.

Sample Input:

101 2 3 4 5 6 7 8 9 0

Sample Output:

6 3 8 1 5 7 9 0 2 4

For BST, the in-order traversal is a non-decreasing sequence, so first sort from small to large, build the tree according to the in-order traversal, and then output according to the serial number (ie, level order traversal):

#include #include using namespace std;int a[1010], n, ans[1010], cnt;void dfs(int x) {if (x <= n) {dfs(x * 2);ans[x] = a[cnt++];dfs(x * 2 + 1);}}int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}sort(a, a + n);dfs(1);for (int i = 1; i <= n; i++) {cout << ans[i];if (i != n) {cout << ' ';}}return 0;}