L2-004 这是二叉搜索树吗？（二叉搜索树与前序遍历的微妙性质）

L2-004 这是二叉搜索树吗？（二叉搜索树与前序遍历的微妙性质）（c++）

题目链接： 这是二叉搜索树吗？

题目描述： 一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点：

其左子树中所有结点的键值小于该结点的键值；

其右子树中所有结点的键值大于等于该结点的键值；

其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入样例：

输入样例1：
7
8 6 5 7 10 8 11
输出样例1：
YES
5 7 6 8 11 10 8

输入样例2：
7
8 10 11 8 6 7 5
输出样例2；
YES
11 8 10 7 5 6 8

输入样例3：
7
8 6 8 5 10 9 11
输出样例3：
NO
           

题解思路： 问题是根据前序遍历来判断是否是二叉搜索树或者是二叉搜索树的镜像，我们根据二叉搜索树的性质再结合二叉树的前序遍历的特点——根左右，可以发现，在前序遍历的基础上：

从前序遍历序列从左到右第一个大于或等于根节点值的那个数
 就是当前根节点的右子树的根节点
 从前序遍历序列从右到左第一个小于根节点值得那个数
 就是当前根节点的左子树的最后的一个结点（即最靠右下的那个结点）
           

根据这个性质，可以先把序列看成是二叉搜索树的前序遍历，然后运用上面的性质，按照后序遍历——左右根的顺序递归，最后根据求的后序遍历的序列的长度和给的前序遍历序列的长度比较是否相等，相等则输出后序序列，不相等则判断时候是镜像二叉搜索树，可以类比搜索二叉树得到类似的性质。

代码如下：

#include<bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define ll long long
#define endl '\n'
#define pb push_back
#define sz size

const int N = 1005;
int n;
int a[N];
vector<int> ans;

void slove(bool flag, int lt, int rt)
{
    if(rt >= lt){
        int i = lt + 1, j = rt;
        if(flag){
            while(i <= rt && a[i] < a[lt])  i++;
            while(j > lt && a[j] >= a[lt])  j--;
            if(i - j != 1) return;
        }
        else{
            while(j > lt && a[j] < a[lt])   j--;
            while(i <= rt && a[i] >= a[lt]) i++;
            if(i - j != 1)  return;
        }
        slove(flag, lt + 1, j);
        slove(flag, i, rt);
        ans.pb(a[lt]);
    }
}

int main()
{
    ios::sync_with_stdio(false);    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    slove(true, 1, n);
    if(ans.sz() == n){
        cout << "YES" << endl;
        for(int i = 0; i < ans.sz(); i++){
            if(i != ans.sz() - 1)   cout << ans[i] << " ";
            else    cout << ans[i] << endl;
        }
    }
    else{
        ans.clear();
        slove(false, 1, n);
        if(ans.sz() == n){
            cout << "YES" << endl;
            for(int i = 0; i < ans.sz(); i++){
                if(i != ans.sz() - 1)   cout << ans[i] << " ";
                else    cout << ans[i] << endl;
            }
        }
        else{
            cout << "NO" << endl;
        }
    }

    return 0;
}