题目:https://pintia.cn/problem-sets/16/problems/669
完全二叉搜索树=完全二叉树+二叉搜索树。从树的形状上来看,一定是从上至下、从左至右摆满的。而树的插入跟输入顺序一点关系也没有,题目中说明了:给定一组输入数据,有唯一的完全二叉搜索树与之对应。
测试样例为:10
1 2 3 4 5 6 7 8 9 0
先来手动建立一下这棵树,有了以下的发现:
- 给定结点数量后,根结点的左右子树各自结点数是可以计算的。
- 根结点可以被唯一确定,即它的大小排在左子树后面。
- 左右子树均为完全二叉搜素树。
有了上面几个条件,我们只需要:
- 将输入数据排序,存放在数组中。
- 递归地确定每一个结点。