PAT甲级1064.

目录

A1064

题目

样例

输入:

10
1 2 3 4 5 6 7 8 9 0

输出:

6 3 8 1 5 7 9 0 2 4

思路和坑点

　　二叉搜索树的中序遍历是有序的，因此排序后，根据次该性质进行计算。完全二叉树的结构可以通过结点数来确定，可以计算出左右子树的结点个数，从而确定树的根结点在中序中的位置，然后递归解决左子树和右子树的根，由于层次序列的整体顺序为root,2*root+1（左子树的根）,2*root+2（右子树的根），因此可以在递归中直接得出层次序列的结点顺序。

AC代码

#include<bits/stdc++.h>
using namespace std;
vector<int> L,v;                                //用于存放数据，L为最终的层次输出序列，v为输入序列 
int getroot(int l,int r){                       //计算输入序列中下标l~r中字数的根，并返回其下标 
    int num=r+1-l,layer=0;                      //num为l~n中的元素个数，layer为该区间元素构成完全二叉树的层数 
    while((int)pow(1.0*2,layer)-1<=num)         //计算layer表示为最大整层数+1 
        layer++;
    layer--;                                    //循环结束，把layer取到最大整层数 
    int flnum=num-((int)pow(1.0*2,layer)-1);    //flnum为最后一层的结点个数 
    int tag=pow(1.0*2,layer-1),leftnum;         //tag为满二叉时，最后一层结点数的一半，leftnum为l~n区间构成的树的左子树元素个数 
    if(flnum<=tag)    leftnum=tag-1+flnum;      //如果最后一层不满一半，计算左子树元素个数 
    else            leftnum=2*tag-1;            //如果满一半，计算左子树个数 
    return leftnum+l;                           //返回根结点所在的下标 
}
void solve(int l,int r,int root){               //将l~n区间中的根结点放置在层次序列的对应位置上 
    if(l>r) return;                             //如果该区间没有元素，直接返回 
    int index=getroot(l,r);                     //计算根在输入序列中的位置 
    L[root]=v[index];                           //将根放在层次序列的位置上 
    solve(l,index-1,2*root+1);                  //递归求解右子树的根 
    solve(index+1,r,2*root+2);                  //递归求解右子树的根 
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int n;
    scanf("%d",&n);
    v.resize(n);    L.resize(n);
    for(int i=0;i<n;i++)
        scanf("%d",&v[i]);
    sort(v.begin(),v.end());                    //排序，搜索树的中序序列是有序的 
    solve(0,n-1,0);                             //递归的起始参数 
    for(int i=0;i<n;i++){                       //输出结果 
        if(i) putchar(' ');
        printf("%d",L[i]);
    }    
    return 0;
}