L2-004 这是二叉搜索树吗？

题目描述

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

输入格式

输入一个正整数n，随后一行给出n个正整数

输出格式

如果该序列是前序遍历的结果，先输出YES ， 下一行输出其后序遍历的结果；否则输出NO

解题思路

我这里只会介绍这题用到的所有知识点，至于完整的知识...我也不会(#^.#) (✪ω✪)

1. 二叉搜索树：对于每一个非叶节点， 其左子树所有节点 小于 该节点 ， 其右子树所有节点 大于等于 该节点。
2. 镜像树：即将所有结点的左右子树对换位置后所得到的树
3. 仅对于二叉搜索树，我们知道后序遍历就可以建树。而对于这个序列而言，左右子树的根分别在两个部分的最右边
4. 前序遍历的根在前面

现在的目的是检查序列是否是 二叉搜索树或其镜像 前序遍历的结果。我们只需要遍历每一个节点，看看它是否是合法的，即每个节点都要满足
上面给出的二叉搜索树的定义。

ac✅️代码

#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
int n;
vector<int> a,post;
bool isMirror = false;
void getpost(int L,int R)
{if( L > R ) return ;int i = L+1, j = R;if(!isMirror){//i是为了找右子树根，j是为了找左子树的右边界一个子树的边界是L+1 到 R，因为最左边是跟while(i <= R && a[i] < a[L]) i++;while(j > L && a[j] >= a[L]) j--;如果全部全部都扫描了一遍，最后i在右子树第一个位置，j在左子树最后一个位置}else {while(i <= R && a[i] >= a[L]) i++;while(j > L && a[j] < a[L]) j--;}if(i - j != 1) return ;//如果是二叉搜索树，每个节点的左右子树在序列中是相邻的，即最后的边界交叉//1. 如果放在这，最后输出的结果是前序遍历getpost(L+1,j);//递归处理左子树//2. 如果放在这，最后输出的结果是中序遍历getpost(i,R);//递归处理右子树//3. 如果放在这，最后输出的结果是后序遍历post.push_back(a[L]);}
int main()
{cin>>n;a.resize(n);for(int i = 0 ; i < n ; i++) cin>>a[i];getpost(0,n-1);if(post.size() != n){isMirror = true;post.clear();getpost(0,n-1);}if(post.size() == n){cout<<"YES"<<endl;for(int i = 0 ; i < n ; i++){    cout<<post[i];if(i != n-1 ) cout <<" ";}cout<<endl;}else cout<<"NO"<<endl;return 0;
}