首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。 例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果: 8 / \ 6 10
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。 例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果: 8 / \ 6 10
admin
2014-11-15
96
问题
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。
例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。
选项
答案
在后续遍历得到的序列中,最后一个元素为树的根结点。从头开始扫描这个序列,比根结点小的元素都应该位于序列的左半部分;从第一个大于跟结点开始到跟结点前面的一个元素为止,所有元素都应该大于跟结点,因为这部分元素对应的是树的右子树。根据这样的划分,把序列划分为左右两部分,我们递归地确认序列的左、右两部分是不是都是二元查找树。 参考代码: using namespace std; /////////////////////////////////////////////////////////////////////// // Verify whether a squence of integers are the post order traversal // of a binary search tree (BST) // Input: squence - the squence of integers // length - the length of squence // Return: return ture if the squence is traversal result of a BST, // otherwise, return false /////////////////////////////////////////////////////////////////////// bool verifySquenceOfBST(int squence[], int length) { if(squence == NULL || length <= 0) return false; // root of a BST is at the end of post order traversal squence int root = squence[length - 1]; // the nodes in left sub-tree are less than the root int i = 0; for(; i < length - 1; ++ i) { if(squence[i] > root) break; } // the nodes in the right sub-tree are greater than the root int j = i; for(; j < length - 1; ++ j) { if(squence[j] < root) return false; } // verify whether the left sub-tree is a BST bool left = true; if(i > 0) left = verifySquenceOfBST(squence, i); // verify whether the right sub-tree is a BST bool right = true; if(i < length - 1) right = verifySquenceOfBST(squence + i, length - i - 1); return (left && right); }
解析
转载请注明原文地址:https://kaotiyun.com/show/oxmZ777K
0
程序员面试
相关试题推荐
Writealettertothedirectorofthelibraryinyouruniversity,givingsomeadviceonhowtoimprovethelibraryservice.You
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。
删除串中指定的字符
列举一下你所了解的XML技术及其应用
添加一个新的类型是计算机管理员的用户John
在PPoint中,对于艺术字的用法,以下说法不正确的是()。A.艺术字是作为文本对象处理的B.艺术字是作为图形对象处理的C.艺术字有多种式样和字体字号D.艺术字可整体缩放
IT服务团队的建设周期中,梯队建设的工作适合在()阶段开展。
下列()不属于项目群的生命周期的一个阶段。
信息系统项目生命周期中,内容最多、最繁杂的阶段是()。
RIPv1与RIPv2的区别是()。
随机试题
股票发行价格可以按票面金额,也可以超过票面金额,同样也可以低于票面金额。()
Pollutionisa"dirty"word.Topollutemeanstocontaminate-topsoilorsomethingbyintroducingimpuritieswhichmake【C1】______
在word2010中,快速访问工具栏上标有“软磁盘”图形的按钮的作用是()文档。
管理信息系统是系统思想建立起来的,以计算机为工具,为管理决策服务的信息系统,简单地说是能够为管理者提供所需信息的系统。下列哪项不属于管理信息系统的特点
种植体形成骨结合的条件是
病理性蛋白尿,可见于
A、冰片B、麝香C、石菖蒲D、苏合香E、安息香治血滞经闭,最宜选用的药物是()
对劳动合同中内容不明确的条款,下列处理方式不恰当的足()。
当市场价格发生变化时,生活必需品的需求()。
WhydidSeanFitzpatrickgotoAmerica?
最新回复
(
0
)