首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
59
问题
输入一整数数组{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
学硕统考专业
相关试题推荐
文艺复兴时期,系统提出了国家主权理论的政治思想家是()。
下列选项中,控制了西域政权的是()
中国第一个资产阶级革命团体兴中会建立的时间是()。
二战后,美国推行“冷战”政策的表现有()①向西欧提供经济援助②支持联邦德国崛起③以联合国名义直接出兵朝鲜④成立北大西洋公约组织
开皇三年,隋文帝下令州县官吏根据户籍簿上登记的年龄,来核对本人体貌,以防诈老诈小逃避租役,是为()。
中国共产党在敌后战场上开创的第一块根据地是()。
根据材料,结合有关知识,回答问题:埃及的河流空了,人(可以)徒步涉过。人们找不到能行船的水。河床变成了沙滩。沙滩上没有水,河床上也没有水……一切好东西都不见了,这个地方枯竭了……土地缩小了,(但是)它的行政人员却很多。土地荒凉不毛;(但)税却很重,只有
1936年,张学良和杨虎城发动的西安事变()。①是一次具有爱国意义的兵变②民族矛盾激化的结果③检验了中国社会各阶级的抗日态度④促成了抗日民族统一战线初步形成
1946年3月5日,英国前首相丘吉尔在富尔敦发表了(),发出第一个明白无误的“冷战”信号。
随机试题
A、Itwillbemorefuturistic.B、Itwillbemoresystematic.C、Itwillbemoreentertaining.D、Itwillbeeasiertounderstand.C
减轻风心病心衰时心脏后负荷风心病心衰时心室率快的房颤
已知某企业2010年~2015年的产品产量统计资料(单位:万件)为:请结合下列选题,给出正确答案。以2013年产品产量为基期水平,每年按4%的速度增长,则2015年的产品产量为()万件。
A石化企业为增值税一般纳税人,2019年3月发生以下业务:(1)从国外某石油公司进口原油50000吨,支付不含税价款折合人民币9000万元,其中包含包装费及保险费折合人民币10万元。(2)开采原油10000吨,并将开采的原油对外销售6000吨,取得含税
培训开发员工的责任最终落实到()身上。
资本主义国家选举的实质是协调统治阶级内部利益关系和矛盾的重要措施。()
WhenIdecidedtoquitmyfulltimeemploymentitneveroccurredtomethatImightbecomeapartofanewinternationaltrend.
甲将一幅名画出售给乙,约定1个月后交付。但丙愿出更高的价格,甲遂将画卖给丙,并当场交付给丙。在此情况下,乙应该怎么办?()
在昏暗的条件下起作用的是()
A、 B、 C、 D、 B
最新回复
(
0
)