输入一整数数组{5,7,6,9,1 1,10,8},该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意

admin2017-04-28  34

问题 输入一整数数组{5,7,6,9,1 1,10,8},该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。要求:

说明你所设计算法的时间复杂度。

选项

答案算法每次确定当前数组中的最后一个为子树的根,然后对数组进行扫描,把数组分成两部分,前面一部分是比根小的,作为左子树,后面一部分比根大的,作为右子树。这个扫描的过程为O(n)。然后递归地构造出整棵树,并判断构造出来的树是否合法。同样地考虑一个递增的数组,每次只能分离出最后一个作为树根,然后往下递归。在这个过程中,第i层的数组里有n—i+1个数,这样总的扫描的次数为n(n—1)/2,所以时间复杂度为O(n2)。 扩展:输入一个整数数组,判断该数组是不是某二叉排序树的前序遍历的结果。该题与前面分析的后序遍历非常类似,只是在前序遍历得到的序列中,第一个数字是根结点的值。

解析
转载请注明原文地址:https://kaotiyun.com/show/9XRi777K
0

最新回复(0)