#include <iostream>
using namespace std;
/**
* 给定一个序列,判断其是不是某个BST的后序遍历输出
* 思想: 根据在位于序列最后的根节点,将序列划分成两个part。
* 然后判断后半序列是否都比root大,如果不是,则返回false。(前半序列一定都比root小)
* 如果当前序列满足BST左右子树两个part的性质,继续递归两个part。
*/
bool judgepostorder(int *a, int n){
//注意边界条件
if(n ==0 || n == 1) return true;
int root = a[n-1];
//找到划分点(第一个大于root的点)
for(int i=0;i<n-1;i++){
if(a[i] > root){
break;
}
}
//如果存在后半序列,则判断是否都大于root
if(i != n-1){
for(int j=i+1;j<n-1;j++){
if(a[j] < root) return false; //不满足
}
}
//各自递归
return judgepostorder(a, i) && judgepostorder(a+i, n-i-1);
}
int main(){
int a[] = {2,4,5,3,9,13,8,6};
int b[] = {2,4,5,3,8,9,3,6};
int c[] = {0};
//int d[] = {};
int f[] = {2,2,2,2};
cout<<judgepostorder(a, 8)<<endl; //1
cout<<judgepostorder(b, 8)<<endl; //0
cout<<judgepostorder(c, 1)<<endl; //1
// cout<<judgepostorder(d, 0)<<endl;
cout<<judgepostorder(f, 4)<<endl; //1
return 0;
}
分享到:
相关推荐
假设输入的数组的任意两个数字都互不相同扩展:判断数组是不是某BST的前序遍历结果使用递归,利用后序遍历的性质bool dfs(int left, int rig
1.1.3 给定一个二叉搜索树(BST),找到树中第 K 小的节点
将bst文件放到MiKTeX的bst文件夹下自己新建的gbt7714-2005文件下,1)作者名称如 KERNER B S 的样式 GBT7714-2005NLang.bst 2)作者名称如 KERNER B S 的样式 GBT7714-2005NLang_UP.bst 3)作者名称如 Kerner B S 的...
BST纠偏调试步骤
该资源为国标参考文献的bst样式文件,GBT7714-2005NLang.bst样式文件。可以在论文参考文献排版时使用
BST纠偏系统调试手册.pdf
BST35206是一款100路1A型继电器开关输出卡
BST34X11是一款PCI/CPCI总线,48路离散量输入/输出卡,其强大的功能能够满足不同用户的工业测量需求,良好的兼容性适用于各类系统配置
BST自动纠偏系统
代码支持《数据结构与算法分析》中的BST数据结构C++代码
Latex修改参考文献展示方式:修改apsrev4-1.bst文件
BST-物料纠偏系统ERK 1000H使用手册pdf,BST-物料纠偏系统ERK 1000H使用手册
舵机供电模块超声波模块供电口舵机模块电机模块红外检测模块检测提示模块电源提示灯亚博 BST-V51 智能小车底板电路原理图。
2、任意输入单词,判断该单词是否在字典中,输出查找的结果,同时请输出单词匹配过程中对比的中间关键字(如果是BST则是树的某一条路径上的单词),思考BST针对顺序输入如何防止退化?请自己提出一种改进策略(区别...
解决springer论文参考文献引用乱序问题
此代码为原创代码 主要描述排序二叉树即BST的创建,以及二叉树的中序遍历,BST的广度遍历下的层序遍历。
BST纠偏操作英文说明pdf,BST纠偏操作英文说明
解决IEE模板同名作者不显示问题,放入到latex目录即可
BST24108 PCI总线,8通道CAN总线通讯卡,光隔离,支持定时发送 BST24208-01 CPCI(3U前出线)总线,8通道CAN总线通讯卡,磁隔离,支持定时发送 BST24212 CPCI(3U前出线)总线,20通道CAN总线通讯卡,磁隔离,支持...
BST-BMP180-DS000-07.pdf英文资料