首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两
admin
2014-04-17
58
问题
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。要求:
说明你所设计算法的时间复杂度。
选项
答案
算法每次确定当前数组中的最后一个为子树的根,然后对数组进行扫描,把数组分成两部分,前面一部分是比根小的,作为左子树,后面一部分比根大的,作为右子树。这个扫描的过程为O(n)。然后递归地构造出整棵树,并判断构造出来的树是否合法。同样地考虑一个递增的数组,每次只能分离出最后一个作为树根,然后往下递归。在这个过程中,第i层的数组里有n—i+1个数,这样总的扫描的次数为n(n一1)/2,所以时间复杂度为O(n
2
)。 扩展:输入一个整数数组,判断该数组是不是某二叉排序树的前序遍历的结果。该题与前面分析的后序遍历非常类似,只是在前序遍历得到的序列中,第一个数字是根结点的值。
解析
转载请注明原文地址:https://kaotiyun.com/show/Olxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
概括指出新民主主义革命各个阶段中国社会的主要矛盾及其表现形式的演变,说明中共根据上述变化对政策的调整及其结果。
《吕氏春秋》载:“公作则迟,有所匿其力也;分地则速,无所匿其力也。”这条材料反映的实质问题是()。
连续五期用全部或大部分的篇幅报道和评论了五四运动这一伟大运动的杂志是()。
中共十六届五中全会提出,建设社会主义新农村的要求是生产发展和()。
汉延熹五年(162)皇甫规得罪宦官,论输左校,太学生()等三百人,跟大官僚一起诣阙陈诉,使皇甫规获得赦免。
《道威斯计划》的实施所产生的直接结果是()。
开皇五年,文帝规定每年正月五日县令出查,令百姓五党三党为一团,根据标准定户等上下,从轻制定税额,并将各户应纳税额写成定簿,是为()。
1942年太平洋战争爆发后,日本先后夺取了焦作、开滦等煤矿,华北沦陷区每年向日本输送的原煤达800万吨。这说明日本在沦陷区进行经济掠夺的直接目的是()。
阅读下列史料,并回答问题:在琶勒尼斯(注:地名)一役获胜后,他(庇西特拉图)便占领政府,并解除人民武装;现在他已能稳定地握住僭主政权,并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的:他在塞修斯庙举行了一个武装的阅兵式,同时举行一次民
序列的“中值记录”指的是:如果将此序列排序后,它是第n/2个记录。试写出一个求中值记录的算法。
随机试题
先进的社会意识之所以能对社会的发展起积极的促进作用,关键在于它()。
Theship______frombehindthefog.
容易发生子宫脱垂的情况有
A.2~4小时B.4~6小时C.6~8小时D.9~11小时E.11~12小时经产妇的第一产程时间()
期货公司向股东或者其关联企业借人的具有次级债务性质的长期借款,可以在计算净资本时将所借入的长期借款按照中国证监会规定的比例计入净资本。( )
小王是某税务机关工作人员,因业务素质不足,导致少征税款10万元。根据刑事法律制度的规定,小王的行为()。
A公司2014年起实施了一系列股权交易计划,具体情况如下。(1)2014年3月10日,A公司与W公司签订协议,协议约定:A公司向W公司定向发行15000万股本公司股票,以换取W公司持有的B公司80%的股权。A公司定向发行的股票按规定为每股3元,双方确定的
根据下面材料回答问题。下图反映了2003—2010年该省城镇居民主要耐用消费品()每百户拥有量的变化趋势。
骨髓分为红骨髓和黄骨髓,其中红骨髓具有造血功能,黄骨髓没有造血功能。()
CustomsofficersataLondonairportyesterdayfound$500,000worthofdrugswhichwerebeingsmuggled(走私)intoBritaininboxes
最新回复
(
0
)