点击链接PAT甲级-AC全解汇总
题目：
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 (≤1000). 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
题意：
输入一串数，组成完全二叉搜索树，并层序输出
我的思路：
发现一个个输入手动都不太好调整，反正结果是唯一的，索性就输入完排序再找对应位置就行。
对于根，左子树都比根小，右子树都比根大，且结点数已知的情况下，可以算出左子树和右子树的个数，那么根节点就是第（左子数个数+1）小的那个数，且根节点永远是在level中第一个位置的，所以得出：
level[根]=第（左子数个数+1）小 的那个数
根据完全二叉树的性质，可以算出：
左子数的个数=（左子树的高度-1 的满二叉树）+（左子树的叶子数）
我的代码：
#include<bits/stdc++.h>
using namespace std;
#define NUMS 1010
int N,nums[NUMS],level[NUMS];//输入当前树结点在nums中最小、最大、根在层的下标
void fun(int first,int last,int root_i)
{
//通过结点个数算出左右子树的个数int n_root=last-first+1;if(!n_root)return;int height_root=log(n_root+1)/log(2);//不算多余叶子的高度int n_root_leaf=n_root-(pow(2,height_root)-1);//叶子个数int n_left_leaf=min(n_root_leaf,(int)pow(2,height_root-1));//左子叶个数int n_left=pow(2,height_root-1)-1+n_left_leaf;//左子节点数//左子个数，根，右子个数level[root_i]=nums[first+n_left];//递归生成左右子树fun(first,first+n_left-1,root_i*2+1);//左子下标2r+1fun(first+n_left+1,last,(root_i+1)*2);//右子下标2(r+1)
}int main()
{
cin>>N;for(int i=0;i<N;i++)cin>>nums[i];sort(nums,nums+N);fun(0,N-1,0);cout<<level[0];for(int i=1;i<N;i++)cout<<" "<<level[i];return 0;
}