首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
89
问题
输入一整数数组{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/wjRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
水门事件
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
洋务派创办军事工业的方式是()。
下列内容,哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张,从经济上瓜分世界
隋朝建立了三省六部制,其中负责审议的部门是()。
判断英国工业革命基本完成的主要依据是()
曾在1978年5月10日《理论动态》上发表的《实践是检验真理的唯一标准》一文,以后又在《光明日报》、《人民日报》、《解放军报》转载,这篇文章的初稿作者是()。
“瓜步之战”发生在下列哪两个政权之间?()
阅读下面史料,回答问题:材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下:合众国525000吨;英帝国525000吨;法国175000吨;意大利175000吨;日本315000吨。
在请求分页存储管理中,若采用FIFO的页面淘汰算法,当分配的页面数增加时,缺页中断的次数()。
随机试题
照片中不规则的颗粒称为
以下执行1类城市区域环境噪声标准的有()。
《建设项目环境保护管理条例》规定,铁路、交通等建设项目,经有审批权的环境保护行政主管部门同意,可以在()报批环境影响报告书或者环境影响报告表。
政府建设主管部门对质量监督人员每()个月进行一次法律法规、业务培训。
某商场室内高度为5.0m,对该商场的消防应急照明和疏散指示系统进行检查,下列检查结果中,不符合现行国家标准《消防应急照明和疏散指示系统技术标准》(GB51309-2018)的是()。
会计师的基本条件包括()。
包裹快递是将用户需要寄送的物品集中到接收地中转站进行分拣、配货、配载,然后再通过接收地网点用小货车送到收货人手中。()
设二叉树的前序序列与中序序列均为ABCDEFGH,则该二叉树的后序序列为
OneofthemostinterestingparadoxesinAmericatodayisthatHarvardUniversity;theoldestinstitutionofhigherlearningin
A、Hehasn’tcompletedhisbiggestcharityprojectuntilnow.B、HegotamessagefromObamaandlawmakers.C、Heaskedforhelpfo
最新回复
(
0
)