3439：【2024年5月】6级算法等考第5题 构造二叉查找树
文件提交：无需freopen
内存限制：256 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
1
提交：1
解决：0
题目描述
## Description
提示信息：
二叉查找树，是指一棵空树或者具有下列性质的二叉树：
1.若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2.若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3.任意节点的左、右子树也分别为二叉查找树。
题目描述
给定n个不同的整数，请按照输入顺序将这些整数依次插入一棵空树中，第一个整数作为根节点，最后构造出一棵包含n个节点的二叉查找树。构造完成后，请输出这棵二叉查找树的深度以及层序遍历序列。
## Input Format
第一行包含一个整数n；
第二行包含n个整数x1，x2，x3，.，xn，其中x1是根节点，整数之间以一个空格隔开。
数据范围
测试点1~10：1≤n≤104，1≤xi≤105。
## Output Format
共两行；
第一行包含一个整数，表示二叉查找树的深度；
第二行包含n个整数，表示二叉查找树的层序遍历序列，整数之间以一个空格隔开。
```input1
7
56 47 35 19 69 80 58
```
```output1
4
56 47 69 35 58 80 19
```
```input2
5
16 20 18 9 25
```
```output2
3
16 9 20 18 25
```