这是二叉搜索树吗
本节内容计 100 分，至少得 100 分可通过
1000ms
32768K
一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：

对于任一结点，其左子树中所有结点的键值小于该结点的键值；
其右子树中所有结点的键值大于等于该结点的键值；
其左右子树都是二叉搜索树。
所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

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

输入格式
输入的第一行给出正整数 N(N≤1000)。随后一行给出 N 个整数键值，其间以空格分隔。

输出格式
如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出YES，然后在下一行输出该树后序遍历的结果。数字间有1个空格，一行的首尾不得有多余空格。

若答案是否，则输出NO。

格式说明
输出时每行末尾的多余空格，不影响答案正确性

输入、输出要求
要求使用「文件输入、输出」的方式解题，输入文件为 search.in，输出文件为 search.out

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

这题做了很久也没过，代码主体思路就是dfs，找到两棵子树的分割点，并向下递归，在只剩下自己一个节点时返回。问了老师，说我找的pos位置错了，还说有可能左子树是正常，右子树是镜像，求修改。

#include<bits/stdc++.h>

using namespace std;

int n, pre[1005], isbst = 1;
int ls[1005], rs[1005];

int dfs(int l1, int r1)
{ 
	//cout << l1 << " " << r1 << endl;
    if(l1 == r1)
    {
        return 0;
    }
    int root = pre[l1];
    int pos, flag = 0, flag2 = (pre[l1 + 1] < root);
    for(pos = l1 + 1; pos <= r1; pos++)
    {
        if(pre[pos] >= root && flag2 == 1||pre[pos] < root && flag2 == 0)
        {
        	flag = 1;
            break;
        }
    }//在pos前分割两棵子树
	if(flag == 0) 
	{
		isbst = 0;
		return 0;
	}
    int lsize = pos - 1 - l1, rsize = r1 - pos + 1;
    ls[root] = dfs(l1 + 1, l1 + lsize);
    rs[root] = dfs(pos, r1);
    return root;
}

void output(int root)
{
	if(ls[root] == 0 && rs[root] == 0)
	{
		return;
	} 
	if(ls[root])
	{
		output(ls[root]);
	}
	if(rs[root])
	{
		output(rs[root]);
	}
	cout << root << " ";
}

int main()
{
    //freopen("search.in", "r", stdin);
    //freopen("search.out", "w", stdout);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> pre[i];
    }
    dfs(1, n);
    if(isbst == 1)
	{
		cout << "YES" << endl;
		output(1);
	}
	else
	{
		cout << "NO";
	}
    return 0;
}