首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回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
113
问题
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回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
程序员面试
相关试题推荐
TheUnitedStatesInterstateHighwaySystemisaninfrastructurefeatofunprecedentedproportions.Notonlydoesitjoinallfi
Weakdollarorno,$46,000—thepriceforasingleyearofundergraduateinstructionamidtheredbrickofHarvardYard—is【C1】__
YouaregoingtostudyabroadandshareanapartmentwithJohn,alocalstudent.Writehimane-mailtotellhimaboutyourli
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。
概述反射和序列化
删除字符串中的数字并压缩字符串(神州数码以前笔试题),如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。(下面的算法只需要一次遍历,不需要开辟新空间,时间复杂度为O(N))
C#中要使一个类支持FOREACH遍历,实现过程怎样?
从当前界面开始,到“电话和调制解调器的选项”中,将系统中的标准56000bps调制解调器删除。
以下关于输入法状态切换的组合键正确的是______A.使用Ctrl+、来切换中文标点和英文标点B.使用Ctrl+空格键来打开或关闭中文输入法C.使用Shift+空格键来切换半角输入模式和全角输入模式D.使用Shift+Ctrl来切换半角输入模式和
论IT服务监督管理监督管理是依据国家IT服务标准对IT服务进行整体评价,并对供方的服务过程、交付结果实施监督和绩效评估。在监督管理环节,需要采取适当的方法,对IT服务全生命周期各个阶段的过程和质量进行度量与评价,并对服务供方的服务过程、交付结果实施监理,
随机试题
在Excel中,用鼠标双击内嵌式图表,则该图表被
一名前臂骨折患者,经手法复位,小夹板固定5h后,感觉剧痛,手指麻木、肿胀、活动不灵,考虑其原因为
挂贴墙面花岗板板材的施工中,所用下列材料属于形成工程实体材料的有()。【2010年真题】
采用喷锚暗挖法施工多层多跨结构隧道时,宜采用的施工方法为()。
税收的作用主要体现在()。(2012年真题题库)
从总体角度来看.利用优惠政策筹划的方法主要包括()。
教学设计者在确定教学的行为目标时,应该清楚地陈述()。
在关系数据库设计中,设计关系模式是数据库设计中______阶段的任务。
Howtoevaluatetheperformanceofstudentsisstillaproblemthattroublesmanyprofessors.
Highstreetshopsuseavarietyofmeanstoattractshoppers,suchasstrikingwindowdisplays,hugered"Sale"signsandspecia
最新回复
(
0
)