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

admin2014-04-17 72

问题输入一整数数组{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/Olxi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

八路军建立的第一个敌后抗日民主根据地是()。

曹操统一北方的关键战役是()。

中国第一条自行设计修建的铁路是在()

下列著作被人们称为17世纪物理学、数学的百科全书，并标志着经典力学体系的完成的是()。

重庆谈判的焦点问题是()

“二战”爆发的原因是多种因素综合作用的结果，其中最根本的因素是()。

光绪皇帝颁布“明定国是”诏书的时间是()。

美国主张建立国际联盟的主要目的是()。

库存台账查询的信息种类有()。

如何正确对待非正式组织的管理?

心理咨询与心理治疗的联系与区别是什么?

A．FⅤB．FⅦC．FⅧD．FⅩE．FⅫ与纤溶酶原的激活有关的是

习惯上所说的“工频”是指电源频率为

内生致热原不包括()。

下列属于成本计算账户的有(　　)。

关于搜查，下列哪一说法是不正确的?()

A．无菌创口B．延期愈合创口C．污染创口D．一期愈合创口E．感染创口早期灼伤和某些化学性损伤已及时处理者()。

Individualsandbusinesseshavelegalprotectionforintellectualpropertytheycreateandown.Intellectualproperty【C1】_______

计算机408

学硕统考专业

八路军建立的第一个敌后抗日民主根据地是()。

曹操统一北方的关键战役是()。

中国第一条自行设计修建的铁路是在()

下列著作被人们称为17世纪物理学、数学的百科全书，并标志着经典力学体系的完成的是()。

重庆谈判的焦点问题是()

“二战”爆发的原因是多种因素综合作用的结果，其中最根本的因素是()。

光绪皇帝颁布“明定国是”诏书的时间是()。

美国主张建立国际联盟的主要目的是()。

库存台账查询的信息种类有()。

如何正确对待非正式组织的管理?

心理咨询与心理治疗的联系与区别是什么?

A．FⅤB．FⅦC．FⅧD．FⅩE．FⅫ与纤溶酶原的激活有关的是

习惯上所说的“工频”是指电源频率为

内生致热原不包括()。

下列属于成本计算账户的有( )。

关于搜查，下列哪一说法是不正确的?()

A．无菌创口B．延期愈合创口C．污染创口D．一期愈合创口E．感染创口早期灼伤和某些化学性损伤已及时处理者()。

Individualsandbusinesseshavelegalprotectionforintellectualpropertytheycreateandown.Intellectualproperty【C1】_______

下列属于成本计算账户的有(　　)。