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

admin2014-04-17 39

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

学硕统考专业

论述一战后德国的赔款问题

下列关于第三次科技革命的说法，不正确的是()。

玛雅人的金字塔主要功能是()。

中国历史上第一部资产阶级革命法典《临时约法》公布的时间是()。

中共十六届五中全会提出，建设社会主义新农村的要求是生产发展和()。

1951年底到1952年春，中国共产党在党政机构工作人员中开展的运动是()。

文艺复兴时期，系统提出了国家主权理论的政治思想家是()。

评析郑和下西洋的历史条件和意义。

《道威斯计划》的实施所产生的直接结果是()。

为什么说在经济全球化背景下，爱国主义并没有也不会过时？

目前单独化疗能治愈的肿瘤是

根据《仲裁法》的相关规定，下列说法正确的有()。

根据《机动车排放污染防治技术政策》，()后国家禁止进口、生产和销售作为汽油添加剂的四乙基铅。

下列费用中，属于施工项目直接成本的是()。

如果出现流动性危机，商业银行采取的下列措施正确的有()。

根据()的不同，公民的民事行为能力分为完全、限制和无民事行为能力人三类。

尝试错误学习的基本规律是效果律、和。

人民警察要树立群众意识，做到“权为民所用，情为民所系，利为民所谋”。(　　)

下列各项中，企业应确认为无形资产的有()

计算机408

学硕统考专业

论述一战后德国的赔款问题

下列关于第三次科技革命的说法，不正确的是()。

玛雅人的金字塔主要功能是()。

中国历史上第一部资产阶级革命法典《临时约法》公布的时间是()。

中共十六届五中全会提出，建设社会主义新农村的要求是生产发展和()。

1951年底到1952年春，中国共产党在党政机构工作人员中开展的运动是()。

文艺复兴时期，系统提出了国家主权理论的政治思想家是()。

评析郑和下西洋的历史条件和意义。

《道威斯计划》的实施所产生的直接结果是()。

为什么说在经济全球化背景下，爱国主义并没有也不会过时？

目前单独化疗能治愈的肿瘤是

根据《仲裁法》的相关规定，下列说法正确的有()。

根据《机动车排放污染防治技术政策》，()后国家禁止进口、生产和销售作为汽油添加剂的四乙基铅。

下列费用中，属于施工项目直接成本的是()。

如果出现流动性危机，商业银行采取的下列措施正确的有()。

根据()的不同，公民的民事行为能力分为完全、限制和无民事行为能力人三类。

尝试错误学习的基本规律是效果律、______和______。

人民警察要树立群众意识，做到“权为民所用，情为民所系，利为民所谋”。( )

下列各项中，企业应确认为无形资产的有()

尝试错误学习的基本规律是效果律、和。

人民警察要树立群众意识，做到“权为民所用，情为民所系，利为民所谋”。(　　)