首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回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
98
问题
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回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
程序员面试
相关试题推荐
RememberNapsterorGrokster?Bothservicesalloweduserstosharecomputerfiles—usuallydigitalmusic—thatinfringedthecopyr
大概描述一下ASP。NET页面的生命周期
数据库的优化设计?
把个人的信息进行设置,显示图片“火箭发射”,与其他人共享网络摄像机功能。
从当前界面上开始操作,把联机用户min邀请加入到对话框中,开始多用户对话。
在桌面上打开帮助和支持中心,利用“索引”的方法取得关于WindowsXP的“磁盘清理程序”方面的帮助信息。
下列叙述正确的是______A.通过“我的电脑”图标可以浏览和使用所有的计算机资源B.“我的电脑”是一个文件夹C.“回收站”用于存放被删除的对象,置入“回收站”中的对象在关机后自动消失D.用户可以在桌面上创建文件夹或快捷方式
在PPoint中,被选中对象虚框上的8个小方框称为()。A.尺寸控制点B.文本插入点C.有效区域范围D.选中对象标记
请对工作簿Book1设置密码123456,同时对其结构进行保护。
由无线终端组成的MANET网络,与固定局域网最主要的区别是__________(23)。在下图所示的由A、B、C三个结点组成的MANET中,圆圈表示每个结点的发送范围,结点A和结点C同时发送数据,如果结点B不能正常接收,这时结点C称为结点A的_______
随机试题
关于地役权法律制度,下列说法正确的是()。
有以下程序#include<stdio.h>intsub(doublea,doubleb){return(int)(a-b-1.3);}main(){printf("%d\n",sub(3.2
简述草拟教育规划的注意事项。
如果企业的普通股市场价格为每股20三,预期下一期的股利为每股1.6元,每年股利增长率预期为6%,那么该普通股的资金成本为()
克罗恩病突发剧烈腹痛和腹肌紧张考虑
压力管道安装单位应当在压力管道安装施工前履行告知手续。承担跨省长输管道安装的安装单位,应当向()履行告知手续。
《会计法》在规定单位负责人为本单位会计行为责任主体的同时,也规定了会计机构、会计人员和其他人员的职责、法律责任。()
就本次你所报考的岗位而言。你认为你的优势和劣势是什么?
一、注意事项1.申论考试是对应试者阅读理解能力、综合分析能力、提出和解决问题能力进行考查的考试。2.作答参考时限:阅读材料40分钟,答卷110分钟。3.仔细阅读给定资料,按照后面提出的申论要求依次作答。4.考生可以在
JourneyinCatastrophes:ThreeFormsofViolentStormsI.WindsandstormsA.Winds’movinginviolentstorms—bringingabout
最新回复
(
0
)