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

admin2017-11-20 55

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

学硕统考专业

1988年起，苏联民族矛盾激化，民族分离运动加剧，第二次较大规模的民族冲突是()。

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

北约和华约两个组织对峙近半个世纪，其影响是()。

下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界

林则徐主持编译的《四洲志》，介绍了世界各国的史地。鸦片战争后，主要以《四洲志》为基础成书的重要著作是()

试分析淝水之战前后南北政局的特点及其变化。

1962年2月，中共中央发出《关于改变农村人民公社基本核算单位问题的指示》，规定人民公社的基本核算单位是()。

西周的官僚制度已经相当完备，官僚机构庞杂，职官名目繁多。周王室的官僚机构分为两大系统，分别是()。

若每年营业现金净流量相等，则投资回收期的计算公式为()

痰热与湿热的舌象相同的表现是()。

印模边缘厚度应为

甲因赌博被A市公安局8区公安分局C派出所处以罚款。甲不服，提出行政复议。本案中可以作为行政复议机关的是(　　)。

下列关于基金组合投资的说法，正确的有()。

与老子、许慎、玄奘、于谦生活时期相对应的朝代是()。

重大飞行事故罪，是指航空人员违反规章制度，因而发生重大飞行事故，危及公共安全，造成严重后果的行为。根据定义，下列属于重大飞行事故罪的是()。

计算机408

学硕统考专业

1988年起，苏联民族矛盾激化，民族分离运动加剧，第二次较大规模的民族冲突是()。

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

北约和华约两个组织对峙近半个世纪，其影响是()。

下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界

林则徐主持编译的《四洲志》，介绍了世界各国的史地。鸦片战争后，主要以《四洲志》为基础成书的重要著作是()

试分析淝水之战前后南北政局的特点及其变化。

1962年2月，中共中央发出《关于改变农村人民公社基本核算单位问题的指示》，规定人民公社的基本核算单位是()。

西周的官僚制度已经相当完备，官僚机构庞杂，职官名目繁多。周王室的官僚机构分为两大系统，分别是()。

若每年营业现金净流量相等，则投资回收期的计算公式为()

痰热与湿热的舌象相同的表现是()。

印模边缘厚度应为

甲因赌博被A市公安局8区公安分局C派出所处以罚款。甲不服，提出行政复议。本案中可以作为行政复议机关的是( )。

下列关于基金组合投资的说法，正确的有()。

与老子、许慎、玄奘、于谦生活时期相对应的朝代是()。

重大飞行事故罪，是指航空人员违反规章制度，因而发生重大飞行事故，危及公共安全，造成严重后果的行为。根据定义，下列属于重大飞行事故罪的是()。

甲因赌博被A市公安局8区公安分局C派出所处以罚款。甲不服，提出行政复议。本案中可以作为行政复议机关的是(　　)。