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

admin2014-04-17 37

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

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

选项

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

解析

转载请注明原文地址:https://jikaoti.com/ti/Y3ajFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

第一国际成立于下面的哪个城市?()

斯大林模式的突出特点是()。

前期的新文化运动不能给灾难深重的中国指明真正的小路，主要是由于()。

蒙古军西征之后，罗斯处于()的控制之下。

以城市为重点的整个经济体制改革的中心环节是()。

波兰三次被瓜分的时间是()

下列科技文化成就，产生于3世纪的是()。①刘徽提出计算圆周率的正确方法②贾思勰著《齐民要术》③钟繇把隶书转化为带书。④马钧发明翻车

简述“事实判断、成因判断和价值判断”三者的相互关系。

已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列

Hehasneverdoneanythingagainstlaw,evenforsuchaminor______asbreakingawindowofhis-eighbor.

35岁，孕39周，G1P0，无痛性阴道出血5h，1h前出现规律宫缩，阴道出血量约500ml，腹部检查ROA，胎头高浮，胎心160次／分，耻骨联合上可闻及与母体脉搏一致的吹风样杂音。该患者最恰当的处理是()

(2011年考试真题)对于需要加工才能对外销售的在产品，下列各项中，属于在确定其可变现净值时应考虑的因素有()。

除息日后股票的价格会下跌，跌幅约为分派的股利。()

课程是自上而下由国家负责编制、实施和评价的教学形式。

年逾花甲的国际机构领导人谈起《论语》来_，一个外国人竟有如此深厚的中华文化功底，让在场嘉宾不禁暗暗__。填入画横线部分最恰当的一项是：

下列说法中错误的是()。

Pleasedon’t________toomuchonthepainfulmemories.Everythingwillbeallright.

以下关于复杂项目管理的描述中，错误的是______。

Inancienttimesthemostimportantexaminationswerespoken,notwritten.IntheschoolsofancientGreeceandRome,testingus

计算机408

学硕统考专业

第一国际成立于下面的哪个城市?()

斯大林模式的突出特点是()。

前期的新文化运动不能给灾难深重的中国指明真正的小路，主要是由于()。

蒙古军西征之后，罗斯处于()的控制之下。

以城市为重点的整个经济体制改革的中心环节是()。

波兰三次被瓜分的时间是()

下列科技文化成就，产生于3世纪的是()。①刘徽提出计算圆周率的正确方法②贾思勰著《齐民要术》③钟繇把隶书转化为带书。④马钧发明翻车

简述“事实判断、成因判断和价值判断”三者的相互关系。

已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列

Hehasneverdoneanythingagainstlaw,evenforsuchaminor______asbreakingawindowofhis-eighbor.

35岁，孕39周，G1P0，无痛性阴道出血5h，1h前出现规律宫缩，阴道出血量约500ml，腹部检查ROA，胎头高浮，胎心160次／分，耻骨联合上可闻及与母体脉搏一致的吹风样杂音。该患者最恰当的处理是()

(2011年考试真题)对于需要加工才能对外销售的在产品，下列各项中，属于在确定其可变现净值时应考虑的因素有()。

除息日后股票的价格会下跌，跌幅约为分派的股利。()

课程是自上而下由国家负责编制、实施和评价的教学形式。

年逾花甲的国际机构领导人谈起《论语》来_________，一个外国人竟有如此深厚的中华文化功底，让在场嘉宾不禁暗暗__________。填入画横线部分最恰当的一项是：

下列说法中错误的是()。

Pleasedon’t________toomuchonthepainfulmemories.Everythingwillbeallright.

以下关于复杂项目管理的描述中，错误的是______。

Inancienttimesthemostimportantexaminationswerespoken,notwritten.IntheschoolsofancientGreeceandRome,testingus

年逾花甲的国际机构领导人谈起《论语》来_，一个外国人竟有如此深厚的中华文化功底，让在场嘉宾不禁暗暗__。填入画横线部分最恰当的一项是：