首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回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
111
问题
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回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
TruthinadvertisingisaconceptcentraltotheAmericanfreemarketeconomicsystem.Accordingtothistheory,companiesthat
RememberNapsterorGrokster?Bothservicesalloweduserstosharecomputerfiles—usuallydigitalmusic—thatinfringedthecopyr
数据库的优化设计?
打开搜狐首页中的【体育】链接,将其中的一幅图片保存到“E:/Tools”文件夹,并将该网页添加到收藏夹中。
从当前界面开始,到“电话和调制解调器的选项”中,将系统中的标准56000bps调制解调器删除。
在金山毒霸2008中,阻止下载运行.ActiveX控件。
请在MSN共享文件会话界面上,利用工具栏添加共享文件,文件位置为“我的文档\注册.txt”。
设置DOS窗口为“快速编辑模式”。
数据库系统的三级模式分别为()模式、内部级模式与外部级模式。
随机试题
正确表示32位二进制地址,最多需要______位十六进制数。
在注射剂生产中常作为除菌滤过的滤器是
某温度时,反应的则反应的=()。
【2014—4】题6~10:某35kV架空配电线路设计采用钢筋混凝土杆、铁横担、钢芯铝绞线,悬式绝缘子组成的绝缘子串,请解答下列关于架空电力线路设计和导线力学计算中的问题。已知该架空电力线路导线的自重比载、冰重比载、自重+冰重比载、无冰时的风压比载、覆
一河段的上断面处有一岸边污水排放口稳定地向河流排放污水,其污水特征为:Qh=19440m3/D,CODcr(h)=100mg/L。河流水环境参数值为:Qp=6.0m3/s,CODcr(p)=12mg/L,u=0.1m/s,kc=0.5L/D。假设污水进入
私募基金管理人自行销售私募基金的,风险揭示书由()签字确认。
若x³+ax²+bx+8有两个因式x+1和x+2,则a+b=()。
关于刑法的体系,下列说法正确的是()
设α1,α2,α3都是矩阵A的特征向量,特征值两两不同,记γ=α1+α2+α3.①证明γ,Aγ,A2γ线性无关,γ,Aγ,A2γ,A3γ线性相关.②设α1,α2,α3的特征值依次为1,-1,2,记矩阵B=(γ,Aγ,A2γ),β=A3γ
The Programming Counter(PC)is normally used to point out(67).
最新回复
(
0
)