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

admin2017-11-20 99

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

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

选项

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

解析

转载请注明原文地址:https://www.kaotiyun.com/show/wjRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

利玛窦与徐光启合作翻译的()，介绍了曾经流行于欧洲的欧几里得平面几何的系统理论，大大地丰富了中国古代几何学的内容。

冶铁技术中的“淬火法”在()已开始应用，大大提高了铁器的坚韧和锋利程度。

秦始皇焚书时未被列入焚书范围的是()。

战国初期，上党地区在下列哪一个国家的控制范围之内?()

下列不属于十一届三中全会过后对各方面社会关系的调整的是()

系统地阐明道家思想的著作《淮南鸿烈》，也叫《淮南子》，是汉武帝时()集宾客写成的。《淮南子》问世时，黄老思想在政治上已不占支配地位了。

(1)所有事件的最早发生时间如下：Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3，ve(3)+6}=12Ve(5)=max{ve(3)+3，ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

奇恒之腑中与肾密切相关的是

A．成牙组织的错构或发育畸形B．良性、单囊或多囊、发生于颌骨内的牙源性肿瘤C．肿瘤生长缓慢，可侵犯包膜，易复发D．有完整包膜．术后很少复发E．为良性肿瘤，呈局部浸润性生长牙瘤()

下面哪项不是窝沟封闭的适应证

下列意识障碍表现中，哪项与颅内血肿关系最为密切

新生儿出生后，Apgar评分的评价指标不包括

马克思认为，人的片面发展最为严重的时期是()

在Windows操作系统中，回收站可以恢复(1)上使用＜Del＞键删除文件或文件夹。在“我的电脑”窗口中，如果要整理磁盘上的碎片，应选择磁盘“属性”对话框(2)选项卡。使用资源管理器时，(3)，不能删除文件或文件夹。

—Lookatthenotesbelow.—Youwillhearawomantelephoningaboutarecruitmentdrive.—staffneededduetogrowthin【9】__