输入一整数数组{5，7，6，9，1 1，10，8}，该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法，判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true，否则返回false。假设输入的数组的任意

admin2017-04-28 76

问题输入一整数数组{5，7，6，9，1 1，10，8}，该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法，判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。要求：

说明你所设计算法的时间复杂度。

选项

答案算法每次确定当前数组中的最后一个为子树的根，然后对数组进行扫描，把数组分成两部分，前面一部分是比根小的，作为左子树，后面一部分比根大的，作为右子树。这个扫描的过程为O(n)。然后递归地构造出整棵树，并判断构造出来的树是否合法。同样地考虑一个递增的数组，每次只能分离出最后一个作为树根，然后往下递归。在这个过程中，第i层的数组里有n—i+1个数，这样总的扫描的次数为n(n—1)/2，所以时间复杂度为O(n²)。扩展：输入一个整数数组，判断该数组是不是某二叉排序树的前序遍历的结果。该题与前面分析的后序遍历非常类似，只是在前序遍历得到的序列中，第一个数字是根结点的值。

解析

转载请注明原文地址:https://www.kaotiyun.com/show/9XRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

简述工农武装割据存在与发展的原因和条件。

在下列我国建国之后的外交活动中，能够体现“和而不同”思想的有()①亚非会议主张“求同存异”②提出“和平共处五项原则”③中日关系实现正常化④同第三世界国家建立友谊

二战后期，反法西斯同盟国召开了一系列会议、达成了一系列协议，以解决战后世界的安排问题，这些会议中以()最为重要，所以，我们将二战后的国际关系格局称为()。

在巴黎和会上获利最大的两个国家是()。

宁夏回族自治区的设立时间是()。

新石器时代的房屋建筑根据环境的不同形成了不同的类型，()地区多为干栏式建筑。

我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说，如炎帝和黄帝两个部落曾战于()，结果黄帝取得了胜利。

5位二进制定点小数，用补码表示时，最小负数是()。

特发性血小板减少性紫癜行脾切除的指征是

“临睡前”的外文缩写为

图5—3—2(a)所示圆轴抗扭截面模量为Wt，切变模量为G，扭转变形后，圆轴表面A点处截取的单元体互相垂直的相邻边线改变了γ角，如图所(b)示。圆轴承受的扭矩T为()。[2009年真题]

根据《建设工程质量管理条例》的规定，施工图必须经过审查批准，否则不得使用，某建设单位投资的大型工程项目施工图设计已经完成，该施工图应该报审的管理部门是()。[2012年真题]

在实施环境质量标准时，应结合所管辖区域环境要素的()和保护目的划分环境功能区。

()是20世纪90年代以来发展最为迅速的一类衍生产品。

企业可以使用固定资产在内的经济活动所产生的收入为基础进行折旧。()

说一件别人误解你的事情，并谈谈你是怎样处理的。