首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{5,7,6,9,1 1,10,8},该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意
输入一整数数组{5,7,6,9,1 1,10,8},该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意
admin
2017-04-28
38
问题
输入一整数数组{5,7,6,9,1 1,10,8},该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。要求:
说明你所设计算法的时间复杂度。
选项
答案
算法每次确定当前数组中的最后一个为子树的根,然后对数组进行扫描,把数组分成两部分,前面一部分是比根小的,作为左子树,后面一部分比根大的,作为右子树。这个扫描的过程为O(n)。然后递归地构造出整棵树,并判断构造出来的树是否合法。同样地考虑一个递增的数组,每次只能分离出最后一个作为树根,然后往下递归。在这个过程中,第i层的数组里有n—i+1个数,这样总的扫描的次数为n(n—1)/2,所以时间复杂度为O(n
2
)。 扩展:输入一个整数数组,判断该数组是不是某二叉排序树的前序遍历的结果。该题与前面分析的后序遍历非常类似,只是在前序遍历得到的序列中,第一个数字是根结点的值。
解析
转载请注明原文地址:https://kaotiyun.com/show/9XRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
二月革命后,俄国为什么会出现两个政权并存的局面?
1901一1939年间美国历届政府在国内经济活动中职能作用的演变。
简论“战时共产主义”政策出台的背景、主要内容及其意义。
下列有关曲辕犁的表述正确的是()①曲辕犁早在中国汉代即已使用了②曲辕犁在中国出现至少比欧洲早一千多年③我国古代的农业工具和农耕技术曾长期居世界领先地位④处于“蒸汽时代”的欧洲农业技术革新,滞后于同时代工业的发
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
“两个凡是”
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
商朝号称青铜时代,下列叙述不符合当时的历史情况的是()
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
随机试题
在Excel2003中,若要选择不相邻的单元格或单元格区域,可以先选定第一个单元格或单元格区域,然后再按住_______键选定其他的单元格或单元格区域。
脊柱骨折合并截瘫的手术指征中,哪几项是恰当的
2008年底,小王欲以自有资金和商用房贷款购买一套价值120万元的商用房。如果小王是以商住两用房名义申请的贷款,银行对于商住两用房的首付比例规定为最低45%,则其贷款额度最大为()万元。
留园留园占地面积约为50余亩,分为东、西、中、北四大景区。西区以山石为奇,堆砌自然险峻,山上一片枫林,极少建筑。北区以田园风光为胜,多植树木,东区和中区是园内景观的集中地带。留园的中区以山池为主体,人们穿过南门,经过幽深的曲径可达“古木交柯”
下列加下划线字中,哪一组为同音字?()
如图所示,在水平台面上放置有一光滑斜面,倾角为α,在斜面上某处放了一根垂直于纸面的直导线,在导线中通有垂直纸面向里的电流,图中α点在导线正下方,b点与导线的连线与斜面垂直,c点在α点左侧,d点在b点右侧。现欲使导线静止在斜面上,下列措施可行的是:
(一)2012年7月31日,国务院新闻办公室在北京举行建军85周年新闻发布会。国防部新闻事务局局长、国防部新闻发言人耿雁生,总参应急办公室副主任吴喜铧,总政办公厅政研室副主任王永胜,总后司令部战勤计划局局长贾祥玉,总装综合计划部综合局副局长林柏,
简述栈、队列、循环队列的定义。
进程P1、P2、P3、P4、P5的前趋关系图如下所示:若用PV操作控制这5个进程的同步与互斥,程序如下:程序中空a和空b处应分别为(48),空c和空d处应分别为(49);空e和空f处应分别为(50)。(48)
(1)在考生文件夹下有一个工程文件sjt3.vbp。程序的功能是通过键盘向文本框中输人大、小写字母和数字。单击标题为“统计”的命令按钮,分别统计输入字符串中大写字母、小写字母及数字字符的个数,并将统计结果分别在标签控件数组x中显示,如图所示。在给
最新回复
(
0
)