首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
31
问题
输入一整数数组{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
学硕统考专业
相关试题推荐
下列口号中不是五四运动期间学生在示威游行时高呼的是()。
第一国际成立于下面的哪个城市?()
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
系统阐明社会主义初级阶段理论是在()。
英国发动鸦片战争的主要目的是()。
1993年,中共十四届三中全会上通过了《中共中央关于解决社会主义市场经济体制若干问题的决定》,其内容不包括()
明代中后期,苏州、松江、嘉兴、()、杭州五府,堪称江南最繁华的城市。
洋务运动中翻译出《几何原本》后九卷、《代数学》、《重学》等数学、物理方面的科技书籍的翻译家是()。
“时方镇缺守帅,稍命文臣权之……又置转运使、通判,为之条禁,文薄渐为精密,由是利归公上而外权削矣。”这段文字反映出北宋初期加强地方控制的基本理念是()。
()的设置是清王朝实行满汉联合、以汉制汉统治方式在军事上的具体体现
随机试题
在明光律师事务所有24名律师,如果有1/2的男律师和1/3的女律师开车去公司上班,那么最多有多少名律师开车上班?
胃溃疡的好发部位是()
Dreamsareoftenanelegantmeansofhighlightingproblems________inthepresentorthepast.
A.青霉素B.红霉素C.庆大霉素D.耐青霉素酶的β-内酰胺类抗生素E.万古霉素支原体肺炎首选
A.营养不足B.红细胞生成相对不是C.消耗增加D.骨髓造血容量减少E.血浆容量增高,血液被稀释红细胞非代偿性增多会出现
蔡某出售伪劣奶粉,被消费者赵、钱、孙、李起诉,蔡某应诉答辩后突然失踪。对此法院应当如何处理?
我国土地所有制是()。
对工程的()有严重影响的关键部位应设置为A级质量控制点。
Duringtheperiodof______fromoilheattogasheatthefurnacewillhavetobeshutoff.
ReturningtoScienceTeresaGarrettwasworkingpart-timeasabiochemistrypostdoc(博士后).Shehadaninfantathome,andsh
最新回复
(
0
)