首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回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
84
问题
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回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
程序员面试
相关试题推荐
TruthinadvertisingisaconceptcentraltotheAmericanfreemarketeconomicsystem.Accordingtothistheory,companiesthat
Weakdollarorno,$46,000—thepriceforasingleyearofundergraduateinstructionamidtheredbrickofHarvardYard—is【C1】__
.什么是code-behind技术
在金山毒霸2008中,阻止下载运行.ActiveX控件。
在桌面上打开“我的电脑”窗口。
在桌面上打开帮助和支持中心,利用“索引”的方法取得关于WindowsXP的“磁盘清理程序”方面的帮助信息。
在幻灯片播放过程中,单击一次鼠标左键会()。A.切换到第一张幻灯片B.切换到最后一张幻灯片C.切换到上一张幻灯片D.切换到下一张幻灯片或本张幻灯片的下一个播放对象
当密码为123456时,请撤消对工作簿Book1的密码及结构保护设置。
信息技术的根本目标是()。
随机试题
法律、行政法规设定的行政许可,其适用范围没有地域限制的,申请人取得的行政许可在全国范围内有效。()
在双因素理论中,与工作的外部环境有关的因素为_____________。
病变多位于大支气管,以中央型多见的肺癌类型包括
层流中流体在进入管道的弯曲部分时,流速的变化为
引起弱视的疾病有
“本年利润”账户的明细分类核算,较适合使用借方贷方多栏式明细分类账的账页格式。
下列关于六西格玛与四西格玛质量的比较正确的有()。
某公司发行面值为100万元、票面利率为8%的优先股票,每年年末付息,发行价格为108万元,承销费用等手续费为5万元,不考虑其他因素,该债券资金成本是()
2007年2月,甲与乙相识,又通过乙结识了丙。三人经协商,达成了去A市买牛皮的协议。同年4月,丙、乙集资1万元,由丙与甲到A市购买牛皮。甲见丙身带钱款,遂生抢劫之念。他以到别处购买牛皮为由,将丙骗出,当行至一隐蔽处,乘丙不备,用石头将丙的头部击伤,丙急忙逃
WhenItellpeoplethatIworkfromwhereverIwant,whetheritbehomeorafriend’soffice,Iamgenerallymetwithabitofs
最新回复
(
0
)