一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，
其左子树中所有结点的键值小于该结点的键值；
其右子树中所有结点的键值大于等于该结点的键值；
其左右子树都是二叉搜索树。
所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。
给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。
输入格式：
输入的第一行给出正整数N（<=1000）。随后一行给出N个整数键值，其间以空格分隔。
输出格式：
如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出“YES”，然后在下一行输出该树后序遍历的结果。数字间有1个空格，一行的首尾不得有多余空格。若答案是否，则输出“NO”。
输入样例1：
7
8 6 5 7 10 8 11
输出样例1：
YES
5 7 6 8 11 10 8
- 思路
二叉搜索树的前序序列除了根之外可以分成一半比它小的，一半比它大的，然后再分别到左右子树递归判断是否满足这个性质，知道没有子树或叶节点的时候停止。镜面二叉树搜索树就是一半大一半小。递归停止条件start>=end
前序转后序，就先根据前面这个性质，分成左右子树，然后递归print左右子树，然后再print这个根结点，递归停止条件strat>end(start==end的时候说明只有一个叶节点这一步也是要执行的应为要cout这个点） - 注意
YES,NO大写的啊！！
#include <iostream>
#define N 1000
using namespace std;
int nums[N];
int flagBT=0;
int flagMBT=0;
int coutflag=0;
void isBT(int start,int endd)
{
if(start>=endd)
return;
int root=nums[start];
int i;
for(i=start+1;i<=endd;++i){
if(nums[i]>=root)
break;
}
int j;
for(j=i;j<=endd;++j){
if(nums[j]<root){
flagBT=1;
break;
}
}
if(!flagBT)
isBT(start+1,i-1);
if(!flagBT)
isBT(i,j-1);
return;
}
void isMBT(int start,int endd)
{
if(start>=endd)
return;
int root=nums[start];
int i;
for(i=start+1;i<=endd;++i){
if(nums[i]<root)
break;
}
int j;
for(j=i;j<=endd;++j){
if(nums[j]>=root){
flagMBT=1;
break;
}
}
if(!flagMBT)
isMBT(start+1,i-1);
if(!flagMBT)
isMBT(i,j-1);
return;
}
void printBT(int start,int endd)
{
if(start>endd)
return;
int root=nums[start];
int i;
for(i=start+1;i<=endd;++i){
if(nums[i]>=root)
break;
}
printBT(start+1,i-1);
printBT(i,endd);
if(coutflag)
cout<<" ";
coutflag=1;
cout<<root;
return;
}
void printMBT(int start,int endd)
{
if(start>endd)
return;
int root=nums[start];
int i;
for(i=start+1;i<=endd;++i){
if(nums[i]<root)
break;
}
printMBT(start+1,i-1);
printMBT(i,endd);
if(coutflag)
cout<<" ";
coutflag=1;
cout<<root;
return;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;++i){
cin>>nums[i];
}
isBT(0,n-1);
isMBT(0,n-1);
if(flagBT&&flagMBT){
cout<<"NO";//大写啊大写啊
}else{
cout<<"YES"<<endl;//大写啊大写啊
if(!flagBT)
printBT(0,n-1);
else
printMBT(0,n-1);
}
return 0;
}
- 我这个方法挺好理解的就是代码不简洁，而且要遍历好多次
print根本不用重开一个方法，在判断的时候就把根放到的一个数组或向量里，如果最后发现不是的话就把这个数组重置一下就行
这里参考了一下这位的方法：https://www.liuchuo.net/archives/2155
思路：先假设式二叉搜索树，按照二叉搜索树的性质，把除根外的部分分成小于它的一半，大于它的一半，但注意如果小部末尾和大部开始不是相邻的话，就说明不是二叉搜索树了，就不要去递归调用它的左右子树了，如果相邻的话就递归，并且最后把这个根放到数组里去，因为有的点因为不满足二叉树的根的性质，就没有被放到数组里，如果数组 长度不等于n的话说明不是二叉树搜索树，然后再按镜面二叉树性质再搜一边，还不等于n的话就是no了，否则就输出那个后序数组。
