problem
L3-010 是否完全二叉搜索树 (30分) 将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。
输入格式： 输入第一行给出一个不超过20的正整数N；第二行给出N个互不相同的正整数，其间以空格分隔。
输出格式： 将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果，数字间以1个空格分隔，行的首尾不得有多余空格。第二行输出YES，如果该树是完全二叉树；否则输出NO。
输入样例1： 9 38 45 42 24 58 30 67 12 51 输出样例1： 38 45 24 58 42 30 12 67 51 YES 输入样例2： 8 38 24 12 45 58 67 42 51 输出样例2： 38 45 24 58 42 12 67 51 NO 作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
给定一个序列，建立一棵二叉搜索树输出层次遍历，并判断是否是完全二叉树
solution
直接当做完全二叉树去建树，如果最后节点编号超过n（即，有奇怪的形状），那么就是NO层次遍历直接扫描序列，有就输出即可。
#include<bits/stdc++.h>
using namespace std
;
const int maxn
= 1010;
int Tree
[maxn
];
void update(int root
, int val
){
if(!Tree
[root
])
Tree
[root
] = val
;
else if(val
> Tree
[root
])
update(root
*2, val
);
else
update(root
*2+1,val
);
}
int main(){
int n
; cin
>>n
;
for(int i
= 1; i
<= n
; i
++){
int x
; cin
>>x
; update(1,x
);
}
int ok
= 0, cnt
= 0;
for(int i
= 1; i
< maxn
; i
++){
if(Tree
[i
]){
if(ok
)cout
<<" ";
else ok
= 1;
cout
<<Tree
[i
];
cnt
= i
;
}
}
if(cnt
> n
)cout
<<"\nNO\n";
else cout
<<"\nYES\n";
return 0;
}
