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

admin2014-04-17 77

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

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

简述近代香港问题的形成。

1971年9月美苏英法四国签署()，肯定了西柏林的占领制度，柏林问题得以解决。

戊戌政变发生的时间是()。

1993年，中共十四届三中全会上通过了《中共中央关于解决社会主义市场经济体制若干问题的决定》，其内容不包括()

明代中后期，苏州、松江、嘉兴、()、杭州五府，堪称江南最繁华的城市。

洋务运动时期，首批赴欧海军留学生派出的时间是()。

()自幼随父在西域成长，深悉西域道里、风土和政治情况。他编著的《西域记》一书，是范晔撰《后汉书.西域传》的重要根据。

中国共产党召开七届二中全会的主要目的是()。

明末清初，著名学者()抗清失败，前往日本讲学，传播中国文化。

1936年，张学良和杨虎城发动的西安事变()。①是一次具有爱国意义的兵变②民族矛盾激化的结果③检验了中国社会各阶级的抗日态度④促成了抗日民族统一战线初步形成

人工关节置换术常见的并发症。

A．癌前病变B．交界性肿瘤C．癌肉瘤D．原位癌E．非肿瘤性病变卵巢浆液性乳头状囊腺瘤，伴非典型增生是

个人收入GPD是指一同以当年价格(或不变价格)计算的个人1年内所得到的收入总和，最主要的扣减项有()。

用友报表系统中，报表公式定义包括()。

将“销售人员”的工资表名称修改为“2014年1月份销售人员工资表”。

()是我国各行各业人员共同的道德规范。

请从所给的四个选项中，选择最合适的一个填入问号处，使之呈现一定的规律性。()

8支球队两两进行比赛，每场获胜可得2分，平局各得1分，输了不得分。一支球队要确保进入前三名，至少应积多少分?

执行下面的程序段后，(AX)=_____。　　　　　　　　　　　　　　　MOV　　CX，5　　　　　　　　　　　　　　MOV　　AX，50　　　　　　　NEXT：　SUB　　AX，CX　　　　　　　　　　　　　　LOOP　NEXT

计算机408

学硕统考专业

简述近代香港问题的形成。

1971年9月美苏英法四国签署()，肯定了西柏林的占领制度，柏林问题得以解决。

戊戌政变发生的时间是()。

1993年，中共十四届三中全会上通过了《中共中央关于解决社会主义市场经济体制若干问题的决定》，其内容不包括()

明代中后期，苏州、松江、嘉兴、()、杭州五府，堪称江南最繁华的城市。

洋务运动时期，首批赴欧海军留学生派出的时间是()。

()自幼随父在西域成长，深悉西域道里、风土和政治情况。他编著的《西域记》一书，是范晔撰《后汉书.西域传》的重要根据。

中国共产党召开七届二中全会的主要目的是()。

明末清初，著名学者()抗清失败，前往日本讲学，传播中国文化。

1936年，张学良和杨虎城发动的西安事变()。①是一次具有爱国意义的兵变②民族矛盾激化的结果③检验了中国社会各阶级的抗日态度④促成了抗日民族统一战线初步形成

人工关节置换术常见的并发症。

A．癌前病变B．交界性肿瘤C．癌肉瘤D．原位癌E．非肿瘤性病变卵巢浆液性乳头状囊腺瘤，伴非典型增生是

个人收入GPD是指一同以当年价格(或不变价格)计算的个人1年内所得到的收入总和，最主要的扣减项有()。

用友报表系统中，报表公式定义包括()。

将“销售人员”的工资表名称修改为“2014年1月份销售人员工资表”。

()是我国各行各业人员共同的道德规范。

请从所给的四个选项中，选择最合适的一个填入问号处，使之呈现一定的规律性。()

8支球队两两进行比赛，每场获胜可得2分，平局各得1分，输了不得分。一支球队要确保进入前三名，至少应积多少分?

执行下面的程序段后，(AX)=_____。 MOV CX，5 MOV AX，50 NEXT： SUB AX，CX LOOP NEXT

执行下面的程序段后，(AX)=_____。　　　　　　　　　　　　　　　MOV　　CX，5　　　　　　　　　　　　　　MOV　　AX，50　　　　　　　NEXT：　SUB　　AX，CX　　　　　　　　　　　　　　LOOP　NEXT　　　　　　　　