【UOJ 572】完整的二进制排序树

二进制排序树是具有以下属性的空树或二进制树:

（1）如果左子树不为空，则左子树上所有节点的值小于其根节点的值;

（2）如果右子树不为空二叉排序树排序，则右子树上所有节点的值都大于其根节点的值；

（3）左右子树也是二进制排序树；

（4）没有节点具有相等的键值.

完整的二叉树: 只有最低的两级节点度可以小于2，最低的节点集中在二叉树的最左侧.

给出N个数字，这些N个数字构成从1到N的排列. 现在您需要按顺序构建一个二进制排序树，并以分层遍历的方式输出它，然后确定它是否是完整的二进制树.

输入包含两行. 第一行是一个正整数N；第二行是从1到N的排列.

输出包含两行. 第一行是构建的二进制排序树的层次遍历；第二行确定它是否是完整的二叉树: 如果输出是，则输出否.

10
7 9 8 4 6 2 10 1 5 3

7 4 9 2 6 8 10 1 3 5
yes

5
3 4 5 2 1

3 2 4 1 5
no

示例1: /

示例2: /

如果看不到图片二叉排序树排序，请下载

时间: 1s空间: 128M

对于100％的数据，1≤N≤20

下载

解决方案: 我想这是最后要写的书了...但是一次通过并不容易.

已经考虑过使用线段树.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-252351-1.html