L2_004这是二叉搜索树吗（判断（镜面）二叉搜索树+前序->后

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，
其左子树中所有结点的键值小于该结点的键值；
其右子树中所有结点的键值大于等于该结点的键值；
其左右子树都是二叉搜索树。
所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。
给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式：
输入的第一行给出正整数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了，否则就输出那个后序数组。