首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回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
54
问题
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回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
程序员面试
相关试题推荐
TruthinadvertisingisaconceptcentraltotheAmericanfreemarketeconomicsystem.Accordingtothistheory,companiesthat
RememberNapsterorGrokster?Bothservicesalloweduserstosharecomputerfiles—usuallydigitalmusic—thatinfringedthecopyr
"Thecatdoesnotofferservices,"WilliamBurroughswrote."Thecatoffersitself."Butitdoessowithunapologeticcontradict
Signslike"Pleaseratemefivestars"pointtoagrowingproblemwithbusinessesintheon-demandeconomyofapp-basedservices
.概述三层结构体系
什么是ASP.net中的用户控件
从“系统属性”出发安装网卡驱动程序。
将桌面背景设置为图片WindowsXP。
从目前技术来看,下列打印机中打印速度最快的是________。
论IT服务监督管理监督管理是依据国家IT服务标准对IT服务进行整体评价,并对供方的服务过程、交付结果实施监督和绩效评估。在监督管理环节,需要采取适当的方法,对IT服务全生命周期各个阶段的过程和质量进行度量与评价,并对服务供方的服务过程、交付结果实施监理,
随机试题
小儿急性持续性腹痛,阵发性加剧并伴有休克,最大可能为
不可以设定行政处罚的是()
两种药物联合应用时:匹鲁卡品与阿托品合用时:
A.肝素B.EDTAC.草酸盐D.分离胶E.枸橼酸盐生化试验应选用的抗凝剂是
患者,女,27岁,产后3d,恶露不下,小腹疼痛阵作、拒按,胸闷喘促,恶心呕吐,突然神昏口噤,不省人事,两手握固,牙关紧闭,面色唇舌俱紫黯,苔少,脉细涩。其诊断是
一些患者在初服某种药物时,由于机体对药物作用尚未适应而引起不可耐受的强烈反应,属于()。
公式“=SUM(A1:B2)”需要对()求和。
()是指仲裁机构在受理当事人仲裁申请后,对案件作出仲裁裁决前,为保证将来仲裁裁决得以实现,而由法院对当事人的财产或争议标的物采取强制措施的制度。
现代社会的社会问题日益增多,许多社会问题单靠民间力量难以解决,因而()开始介入人民的社会生活,以公共行动的方式去解决人们的社会问题。
认知内驱力、自我提高内驱力和附属内驱力在动机结构中所占的比重并非一成不变。在()附属内驱力最为突出。
最新回复
(
0
)