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

admin2017-11-20 35

问题输入一整数数组{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/wjRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

电子计算机的发展经过了四代，①电子数值积分计算机(ENIAC)；②集成电路计算机；③大规模集成电路计算机；④晶体管计算机；⑤人工智能计算机，其先后顺序是()。

1994年5月，江泽民在进一步强调正确处理改革、发展、稳定的关系时指出()。

世界天文史上最早实地测量子午线的记录是由谁进行的?()

中国共产党制定的抗日民族统一战线策略总方针的中心环节是()。

明中叶后，商业资本比较活跃，活动于全国范围的商人和商帮中最为著名的是()。

第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式，最早提出这种方式的是()

材料一从波罗的海斯德丁(什切青)到亚得里亚海边的里亚斯特，一幅横贯欧洲大陆的铁幕已经降落下来……无一不处在苏联的势力范围之内。

隋朝建立了三省六部制，其中负责审议的部门是()。

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

公募基金定期披露的报告包括()。Ⅰ．月度报告Ⅱ．季度报告Ⅲ．半年度报告Ⅳ．年度报告

WhichofthefollowingdescriptionsofThomasHardyiswrong?()

男孩，15岁。急起畏寒、发热2天，伴精神萎靡、烦躁不安。查体：全身皮肤黏膜有广泛的瘀点、瘀斑，脑膜刺激征阴性。血象：WBC20．0×109／L，NO．90，LO．10。为快速诊断提供依据，应做哪项检查

施工资源管理任务中，“确定资源的选择”不包括(　　)工作。

(　　)使得每项工程都要根据实际情况制定健康安全与环境管理计划。

个人银行储蓄账户既可以办理现金存取业务，也可以办理转账结算业务。()

旅游团北戴河时，一游客提出希望单独划船出海，导游员应()

Withoutcomputers,muchoftheadvancedtechnology______.

MediaSelectionforAdvertisementsA)Afterdeterminingthetargetaudienceforaproductorservice,advertisingagenciesmusts

计算机408

学硕统考专业

电子计算机的发展经过了四代，①电子数值积分计算机(ENIAC)；②集成电路计算机；③大规模集成电路计算机；④晶体管计算机；⑤人工智能计算机，其先后顺序是()。

1994年5月，江泽民在进一步强调正确处理改革、发展、稳定的关系时指出()。

世界天文史上最早实地测量子午线的记录是由谁进行的?()

中国共产党制定的抗日民族统一战线策略总方针的中心环节是()。

明中叶后，商业资本比较活跃，活动于全国范围的商人和商帮中最为著名的是()。

第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式，最早提出这种方式的是()

材料一从波罗的海斯德丁(什切青)到亚得里亚海边的里亚斯特，一幅横贯欧洲大陆的铁幕已经降落下来……无一不处在苏联的势力范围之内。

隋朝建立了三省六部制，其中负责审议的部门是()。

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

公募基金定期披露的报告包括()。Ⅰ．月度报告Ⅱ．季度报告Ⅲ．半年度报告Ⅳ．年度报告

WhichofthefollowingdescriptionsofThomasHardyiswrong?()

男孩，15岁。急起畏寒、发热2天，伴精神萎靡、烦躁不安。查体：全身皮肤黏膜有广泛的瘀点、瘀斑，脑膜刺激征阴性。血象：WBC20．0×109／L，NO．90，LO．10。为快速诊断提供依据，应做哪项检查

施工资源管理任务中，“确定资源的选择”不包括( )工作。

( )使得每项工程都要根据实际情况制定健康安全与环境管理计划。

个人银行储蓄账户既可以办理现金存取业务，也可以办理转账结算业务。()

旅游团北戴河时，一游客提出希望单独划船出海，导游员应()

Withoutcomputers,muchoftheadvancedtechnology______.

MediaSelectionforAdvertisementsA)Afterdeterminingthetargetaudienceforaproductorservice,advertisingagenciesmusts

施工资源管理任务中，“确定资源的选择”不包括(　　)工作。

(　　)使得每项工程都要根据实际情况制定健康安全与环境管理计划。