Complete Binary Search Tree 完全二叉搜索树

题目:https://pintia.cn/problem-sets/16/problems/669

完全二叉搜索树=完全二叉树+二叉搜索树。从树的形状上来看,一定是从上至下、从左至右摆满的。而树的插入跟输入顺序一点关系也没有,题目中说明了:给定一组输入数据,有唯一的完全二叉搜索树与之对应。

测试样例为:10

      1 2 3 4 5 6 7 8 9 0

先来手动建立一下这棵树,有了以下的发现:

Complete Binary Search Tree 完全二叉搜索树

  1. 给定结点数量后,根结点的左右子树各自结点数是可以计算的。Complete Binary Search Tree 完全二叉搜索树
  2. 根结点可以被唯一确定,即它的大小排在左子树后面。
  3. 左右子树均为完全二叉搜素树。

有了上面几个条件,我们只需要:

  1. 将输入数据排序,存放在数组中。
  2. 递归地确定每一个结点。

Complete Binary Search Tree 完全二叉搜索树

 

Complete Binary Search Tree 完全二叉搜索树

上一篇:AT4995-[AGC034E] Complete Compress【树形dp】


下一篇:R语言-使用箱型图进行数据异常值分析