首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回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
69
问题
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回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
程序员面试
相关试题推荐
Theimmunesystemisequalincomplexitytothecombinedintricaciesofthebrainandnervoussystem.Thesuccessoftheimmune
RememberNapsterorGrokster?Bothservicesalloweduserstosharecomputerfiles—usuallydigitalmusic—thatinfringedthecopyr
"Thecatdoesnotofferservices,"WilliamBurroughswrote."Thecatoffersitself."Butitdoessowithunapologeticcontradict
一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。求总共有多少总跳法,并分析算法的时间复杂度。
在Google搜索引擎中搜索多个关键词“office”,“WPS”。
设置TCP/IP属性的备用DNS服务器地址202.112.88.31。
请对工作簿Book1设置密码123456,同时对其结构进行保护。
论IT服务规划设计IT服务规划设计处于IT服务生命周期的前期,如果前期未进行有效的规划设计,那么仓促而就的IT服务就难以满足客户的真正需求,可能造成IT服务可用性降低、客户满意度低下等问题。为确保有效做好IT服务规划设计,服务供方在IT服务规划设计过程中
病毒和木马的根本区别是______。
移动通信4G标准与3G标准最主要的区别是___________(25),当前4G标准有___________(26)。(26)
随机试题
电阻应变片式称重传感器的输出电阻一般大于输入电阻。
A.八正散B.六磨汤C.清肺饮D.沉香散患者小便不通,小腹胀满,口苦咽干,舌红苔腻,脉滑数,治宜选用
女性,32岁。主诉右乳胀痛,与月经周期有关,检查乳房有多个结节状肿块,边界不清,可推动。诊断首先考虑
药典规定对阿司匹林进行碳酸钠液澄明中度检查,为检测杂质
补风量不应小于排烟量的()。
某国有工业企业,2014年3月份因雷击造成火灾,共计损失250万元,其中,流动资产损失90万元;固定资产损失160万元。企业收到保险公司的赔偿款100万元,其中,流动资产保险赔偿款70万元,固定资产保险赔偿款30万元。企业由于这次火灾损失而应计入营业外支出
数据模型的三要素是数据结构、数据操作和()。
小李是小学四年级的一名学生,同学们都不喜欢他,没有人愿意和他玩,老师们说起他都是直摇头,还有老师断言,小李啊,长大之后就是一个小混混。原来,小李有个非常坏的毛病,那就是喜欢欺负同学。小李经常管比自己小的同学要保护费,别人不给他,他就揪着人家的衣领一顿打,受
你可能会遇上一位深藏不露的智者,其不经意间的一句话让你_____________;也可能会碰上一位令你心动的小伙或姑娘,铁轨的轰鸣声也无法干预你_____________注视的目光;或者走遍_____________,你才恰好在火车上得了一剂妙手回春的药方
巡逻警察简称“巡警”,是指在一定路线或一定地段用巡逻方式进行勤务活动的人民警察。()
最新回复
(
0
)