OJ：https://www.patest.cn/contests/pat-a-practise/1064
（一）23分（3个case未过）代码
建树的规律是我瞎猜的。首先用样例数据分析。
10 1 2 3 4 5 6 7 8 9 0
对数据排序后：
0 1 2 3 4 5 6 7 8 9
有10个数据，因为是完全二叉树，底层应该有3个叶子，上层有1+2+4=7个结点。用以下代码计算：
int up_num=1,t=1; while(up_num + t*2 < n){ t*=2; up_num+=t; } int leaves_num=n-up_num;
0 1 2 | 3 4 5 6 7 8 9
将左侧叶子结点分割开，对右侧结点进行分析。
6就是根结点。计算方式是取中间。这个算法中所有的“取中间”都满足以下规律：
奇数个数：直接取中间
偶数个数：取中间靠右
定义以下函数计算：
int get_mid(int a,int b){ if((a+b)%2){ return (a+b)/2+1; } return (a+b)/2; }
6就是从3到9取中间而来。之后就可以递归建树了。
6的左叶子是0到5取中间的3。
6的右叶子是7到9取中间的8。
……
23分代码：
#include <stdio.h> #include <memory.h> #include <math.h> #include <string> #include <vector> #include <set> #include <stack> #include <queue> #include <algorithm> #include <map> #define I scanf #define OL puts #define O printf #define F(a,b,c) for(a=b;a<c;a++) #define FF(a,b) for(a=0;a<b;a++) #define FG(a,b) for(a=b-1;a>=0;a--) #define LEN 1010 #define MAX (1<<30)-1 #define V vector<int> using namespace std; int a[LEN]; int n; typedef struct Node{ int d; struct Node* l=NULL; struct Node* r=NULL; Node(int d=0):d(d){ } }; int get_mid(int a,int b){ if((a+b)%2){ return (a+b)/2+1; } return (a+b)/2; } Node * build_tree(int s,int e) { if(e<s) return NULL; if(e==s) return new Node(a[s]); int t=get_mid(s,e); Node *node=new Node(a[t]); node->l=build_tree(s,t-1); node->r=build_tree(t+1,e); return node; } int main(){ // freopen("1064.txt","r",stdin); I("%d",&n); int i; FF(i,n) I("%d",&a[i]); sort(a,a+n); int up_num=1,t=1; while(up_num + t*2 < n){ t*=2; up_num+=t; } int leaves_num=n-up_num; int root_i=get_mid(leaves_num,n-1); Node *root=new Node(a[root_i]); root->l=build_tree(0,root_i-1); root->r=build_tree(root_i+1,n-1); queue<Node*> q; q.push(root); int cnt=0; while(!q.empty()){ Node* tmp=q.front(); q.pop(); cnt++; O("%d",tmp->d); if(cnt<n) O(" "); if(tmp->l) q.push(tmp->l); if(tmp->r) q.push(tmp->r); } return 0; }
看了大佬的博客之后，才知道自己是多么naive。这题其实很简单，利用BST的性质：中序遍历的序列递增有序，再用dfs（其实深搜的本质就是中序遍历）和一个二叉堆来递归建树。最后都不用队列来模拟层序，直接把二叉堆依次输出就可以了。
AC代码：
#include <stdio.h> #include <memory.h> #include <math.h> #include <string> #include <vector> #include <set> #include <stack> #include <queue> #include <algorithm> #include <map> #define I scanf #define OL puts #define O printf #define F(a,b,c) for(a=b;a<c;a++) #define FF(a,b) for(a=0;a<b;a++) #define FG(a,b) for(a=b-1;a>=0;a--) #define LEN 10010 #define MAX 0x06FFFFFF #define V vector<int> using namespace std; int n; int a[LEN] ,ans[LEN]; int p=-1; //p是中序遍历序列的索引，初始化为-1，因为在操作中首先会被+1而变成0 void dfs(int x){ //x是二叉堆（完全二叉树）的索引，根节点是0，叶子节点满足二倍关系 if(x>=n){ //超出界限 p++; //进行了一轮超出界限的操作，意味着操作序列的更新 return; //记得退出，不然会爆栈。找到目标解或者到了递归边界而退出是dfs的必须操作 } dfs(x*2+1); //左子树递归 ans[x]=a[p]; //ans数组就是二叉堆，a是中序遍历序列。 dfs(x*2+2); //右子树递归 } int main(){ // freopen("D:\input\A1064.txt","r",stdin); I("%d",&n); int i; FF(i,n) I("%d",&a[i]); sort(a,a+n); dfs(0); FF(i,n){ O("%d",ans[i]); if(i!=n-1) O(" "); } return 0; }