首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两
输入一整数数组{5,7,6,9,11,10,8},该整数序列为图2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两
admin
2017-11-20
39
问题
输入一整数数组{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://jikaoti.com/ti/PWfjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
夏王朝建立后,将其领土划分为九州,派九牧进行治理,在九州范围内根据土地的肥沃程度缴纳贡赋,称为()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
毛泽东认为,社会主义这个阶段可分为两个阶段,包括()。
“我不想变成上帝,或居住在永恒之中,或者把天地抱在怀里,属于人的那种光荣对我就够了。我自己是凡人,我只要求凡人的幸福。”这句话体现的思想是()
第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式,最早提出这种方式的是()
战时共产主义政策中对后来的工农联盟最能构成威胁的是()。
《道威斯计划》的实施所产生的直接结果是()。
第一次国共合作采取了共产党员以个人身份加入国民党的党内合作方式,最早提出这种方式的是()。
判断英国工业革命基本完成的主要依据是()
阅读下面史料,回答问题:材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下:合众国525000吨;英帝国525000吨;法国175000吨;意大利175000吨;日本315000吨。
随机试题
边际技术替代率是指()
简述牙菌斑微生物作为牙周病始动因子的证据。
治疗失眠宜选用的药物是
甲省A市检察院根据当事人的申诉,发现甲省A市中级人民法院作出的生效判决认定事实确实存在错误,则甲省A市检察院的下列做法中正确的有:()
广义的工程项目管理指开发建设项目施工阶段的管理,对房地产开发项目而言,工程项目管理工程通常取广义的理解。()
根据现行财务制度的规定,在承包企业中,对于技术进步较快或使用寿命受工作环境影响较大的施工机械和运输设备,经财政部批准,计提折旧时可以采用的方法有()。
年末,华力公司主管财务会计工作的副总经理王某召集财务部部长李某及相关人员开会,重点研究本年财务决算的相关事宜,同时财务部汇报几项工作,由领导决定。以下是会议期间的部分发言:王某:受金融危机的影响,公司今年的内销及外销均大幅度下滑,亏损已成定局。财务部正在
甲公司因拖欠乙公司货款被乙公司诉至法院,乙公司胜诉后甲公司拒不执行,乙公司向法院申请强制执行。甲公司知晓后将公司财产陆续转移。下列说法不正确的是()。
A、 B、 C、 B
AspectsthatMayFacilitateReadingI.Determiningyour【T1】______【T1】______A.Readingfor【T2】______:【T2】______likeread
最新回复
(
0
)