首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。 例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果: 因此返回true。 如果输入7、4、6、5,没有哪棵树的后序遍历
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。 例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果: 因此返回true。 如果输入7、4、6、5,没有哪棵树的后序遍历
admin
2019-03-29
107
问题
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。
例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:
因此返回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); }
解析
这是一道trilogy的笔试题,主要考查对二元查找树的理解。
在后续遍历得到的序列中,最后一个元素为树的根结点。从头开始扫描这个序列,比根结点小的元素都应该位于序列的左半部分;从第一个大于跟结点开始到跟结点前面的一个元素为止,所有元素都应该大于跟结点,因为这部分元素对应的是树的右子树。根据这样的划分,把序列划分为左右两部分,我们递归地确认序列的左、右两部分是不是都是二元查找树。
转载请注明原文地址:https://kaotiyun.com/show/BxmZ777K
0
程序员面试
相关试题推荐
[A]Theperson-skillsmatchapproachtoselection[B]Theimpactsofbadselectiondecisions[C]Theimportanceofstructu
Writeanessaybasedonthefollowingoutline.Youshouldwriteabout150wordsontheANSWERSHEET.1.教师用课外时间给学生补课赚钱的现象
输入一个链表的头结点,反转该链表,并返回反转后链表的头结点。链表结点定义如下:{intm_nKey;ListNode*m_pNext;};
删除字符串中的数字并压缩字符串(神州数码以前笔试题),如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。(下面的算法只需要一次遍历,不需要开辟新空间,时间复杂度为O(N))
根据委托(delegate)的知识,请完成以下用户控件中代码片段的填写:namespacetest{publicdelegatevoidOnDBOperate();publicclassUserControlBase
将远程服务器中名为“通知”的文件在不下载的情况下进行编辑,修改201教室为303教室,然后直接保存,并在关闭编辑窗口后上传。
在桌面上打开帮助和支持中心,利用“索引”的方法取得关于WindowsXP的“磁盘清理程序”方面的帮助信息。
请在当前幻灯片中的图形前添加一个形状,并输入“技术部”。
任何一个团队从开始组建到最终达到绩效要求,需要一个周期。依据塔克曼群体发展模型,结合IT服务管理工作特性,将团队建设周期分为四个阶段,它们分别是(未按正确次序排列):①风暴期②表现期③组建期④规范期团队建设周期的正确排序为______。
RIPv1与RIPv2的区别是()。
随机试题
既能治疗水肿,脚气肿痛,又能治疗疟疾的药物是
检测细胞因子一般不采用
由于资源的稀缺性及(),节约资源是实现可持续发展的重要途径之一。
下列建筑物中,属于民用建筑的是()。
基金管理人的基金宣传推介材料,应自向公众分发或者发布之日起()个工作日内向中国证监会派出机构备案。
2013年2月份,甲股份有限公司(以下简称甲公司)聘请注册会计师对其2012年度的财务会计报告进行审计,所聘注册会计师在审计过程中,对甲公司以下交易或事项的会计处理提出异议:(1)2012年5月8日,甲公司与A公司签订合同,向A公司销售某大型设备。该
下列现象中利用了熔化吸热的是()。
(1996年)设则a=________.
数据库的逻辑模型设计阶段的主要任务是将【】转换成关系模型。
______coolitistotakeapicturewithYaoMin!
最新回复
(
0
)