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

admin2017-11-20 86

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

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

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

印加人记载事物使用的方法是()。

材料一从波罗的海斯德丁(什切青)到亚得里亚海边的里亚斯特，一幅横贯欧洲大陆的铁幕已经降落下来……无一不处在苏联的势力范围之内。

把变量引进数学。使解析几何成为数学发展史上转折点的科学家是()。

1962，中共中央调整计划目标，工业生产值原定950亿元调为880亿元，钢产量755万吨调为600万吨，并按“经济合理，保留骨干的原则，对企业关停并转。这举措目标

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。

有关痰液在各种肺部疾病中的表现，错误的组合是()。

编码氨基酸的遗传密码共有

(2013年第66题)与幽门螺杆菌感染无关的疾病是

2007年8月，根据《期货交易管理条例》及相关法规和规范性文件，中国证券监督管理委员会发布了()，建立了“五位一体”的期货监管协调工作机制。

()不属于场地拓展训练游戏。

跳高的姿势可以分为___、剪式、_、仰卧式、_、___六种。

课程是教师、学生、教材、环境四个因素动态交互作用的“生态系统”。()

据统计，被指控抢劫的定罪率要高于被指控贪污的定罪率。其重要原因是贪污案的被告能聘请到收费最高的律师，而抢劫案的被告主要是由法庭指定的律师辩护。以下哪项为真，最能支持题千的叙述?()

It’sanindustrybuiltpurely【C1】______image,buttheactors,actressesandsingerswhoturntoitforhelpliketokeepita

计算机408

学硕统考专业

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

印加人记载事物使用的方法是()。

材料一从波罗的海斯德丁(什切青)到亚得里亚海边的里亚斯特，一幅横贯欧洲大陆的铁幕已经降落下来……无一不处在苏联的势力范围之内。

把变量引进数学。使解析几何成为数学发展史上转折点的科学家是()。

1962，中共中央调整计划目标，工业生产值原定950亿元调为880亿元，钢产量755万吨调为600万吨，并按“经济合理，保留骨干的原则，对企业关停并转。这举措目标

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。

有关痰液在各种肺部疾病中的表现，错误的组合是()。

编码氨基酸的遗传密码共有

(2013年第66题)与幽门螺杆菌感染无关的疾病是

2007年8月，根据《期货交易管理条例》及相关法规和规范性文件，中国证券监督管理委员会发布了()，建立了“五位一体”的期货监管协调工作机制。

()不属于场地拓展训练游戏。

跳高的姿势可以分为_______、剪式、_______、仰卧式、_______、_______六种。

课程是教师、学生、教材、环境四个因素动态交互作用的“生态系统”。()

据统计，被指控抢劫的定罪率要高于被指控贪污的定罪率。其重要原因是贪污案的被告能聘请到收费最高的律师，而抢劫案的被告主要是由法庭指定的律师辩护。以下哪项为真，最能支持题千的叙述?()

It’sanindustrybuiltpurely【C1】______image,buttheactors,actressesandsingerswhoturntoitforhelpliketokeepita

跳高的姿势可以分为___、剪式、_、仰卧式、_、___六种。