目录

1，题目描述

题目大意

2，思路

数据结构

算法

3，AC代码

4，解题过程

1，题目描述

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

题目大意

给出一系列数字，构造完全二叉搜索树（完全二叉树第i层至多有2^（i-1）个节点），并输出层次遍历序。

2，思路

数据结构

• struct node{int value, levelOrder;}：value存放节点的值，levelOrder存放标明层次遍历顺序的值（越小越靠前）；
• vector<node> tree：存放所有节点数据；

算法

参照题目中的例子：

1. 将输入序列从小到大排序0，1，2……9（即最终构造的树的中序遍历）；
2. 根据二叉搜索树的特点，确定树的层数，左子树节点个数，进而确定根节点，左右子树根节点的位置（由于搜索树本身比较特殊，再加上是完全二叉树，所以可以根据中序遍历，确定一棵树），并递归遍历左右子树；
3. 确定根节点后，将函数中携带的order赋值给他（void getLevelOrder(int head, int tail, int order)），递归遍历左右子树时将order分别修改为2*order+1和2*order+2；

   getLevelOrder(head, root - 1, 2 * order + 1);
   getLevelOrder(root + 1, tail, 2 * order + 2);

    

3，AC代码

#include<bits/stdc++.h>
using namespace std;
struct node{
    int value, levelOrder;
};

int flag = 0, N;                                    //flag排序的依据 N节点数目
vector<node> tree;

bool cmp1(node a, node b){
    if(flag == 0) return a.value < b.value;
    else return a.levelOrder < b.levelOrder;
}
void getLevelOrder(int head, int tail, int order){
    if(head > tail) return;                         //递归出口
    if(head == tail){
        tree[head].levelOrder = order;
        return;
    }
    
    int numOfNode = tail - head + 1;                //叶子数目
    int depth = 1;                                  //树的深度
    while(pow(2, depth) - 1 <= numOfNode)
        ++depth;
    depth--;                                        //锁定到全部填满的一层

    int leftNodes = 0;                              //左子树节点个数
    int leafNum = numOfNode - (pow(2, depth) - 1);  //叶子数目
    if(leafNum > pow(2, depth-1))
        leftNodes += pow(2, depth-1);
    else
        leftNodes += leafNum;
    leftNodes += (pow(2, depth) - 1) / 2;           

    int root = head + leftNodes;                    //根据左子树节点个数以及head位置 锁定root下标
    tree[root].levelOrder = order;                  //层次遍历的次序
    getLevelOrder(head, root - 1, 2 * order + 1);
    getLevelOrder(root + 1, tail, 2 * order + 2);
}

int main(){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGE

	cin>>N;
	int x;
	for(int i = 0; i < N; i++){
        scanf("%d", &x);
        tree.push_back({x, 0});
	}
	sort(tree.begin(), tree.end(), cmp1);           //按照value大小排序
	getLevelOrder(0, N-1, 0);
	flag = 1;
	sort(tree.begin(), tree.end(), cmp1);           //按照层次遍历的顺序排序

	printf("%d", tree[0].value);
	for(int i = 1; i < N; i++){
        printf(" %d", tree[i].value);
	}

    return 0;
}

4，解题过程

一发入魂