首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{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
34
问题
输入一整数数组{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
学硕统考专业
相关试题推荐
简述商鞅变法的主要内容。
【《关于正确处理人民内部矛盾的问题》】
西南军阀跟随孙中山拥护护法运动的目的是()。
宁夏回族自治区的设立时间是()。
巴黎和会上,英美主张把原德国在山东的权利转让给日本,华盛顿会议又表示支持中国让日本归还山东的要求,英美态度发生变化的根本原因是()。
下列有关《布列斯特和约》的说法中,错误的一项是()。
阅读材料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为仁,以神
东印度公司
玛雅人的金字塔主要功能是()。
已知一个带有表头结点的单链表,结点结构为:假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0。要求:
随机试题
控制切屑流出方向的是铣刀的()。
把基础研究发现的新理论用于特定目标的研究属于()
A.天冬酰胺B.磷酸核糖C.甘氨酸D.谷氨酸上述物质中不是嘌呤核苷酸从头合成的直接原料是
子宫内膜的周期性变化超声特点是
A、 B、 C、 D、 A,B
我国现行建设项目投资构成和工程造价的构成中,()是指根据国家有关规定在投资中支付,并列入建设项目总造价或单价工程造价的费用。
某超市为增值税小规模纳税人。2006年1月,该超市取得货物零售收入120000元;向困难群体捐赠部分外购商品,捐赠商品的买价为4200元,售价为5000元;向职工发放部分外购商品作为节日福利,发放商品的买价为3000元,售价为3700元;销售已使用1年的冰
专业软件销售人员由于需要较高的专业知识且销售工作的周期较长,所以其薪酬应采用()。
以下不属于存储器的是()。
Mostpeopleagreethatfencing(击剑)isonesportinwhichapersonmustbeatleast30yearsoldbeforehelearnsallheneedst
最新回复
(
0
)