这是二叉搜索树吗？

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

• 其左子树中所有结点的键值小于该结点的键值；
• 其右子树中所有结点的键值大于等于该结点的键值；
• 其左右子树都是二叉搜索树。

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

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

输入格式：

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

输出格式：

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

输入样例 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
using namespace std;
struct Node{
	int data;
	Node *l;
	Node *r;
};
vector<int>s,pre1,pre2,post1,post2;
 
//先构造树 
Node *build(Node *root,int x){
	if(root==NULL){
		root = new Node;
		root->l = root->r = NULL;
		root->data = x;
	}else if(xdata){  //小于根节点说明是左子树 
		root->l = build(root->l,x);
	}else{   //大于根节点说明是右子树 
		root->r = build(root->r,x);
	}
	return root;
} 
 
void preorder1(Node *root){  //前序遍历（根左右） 
	if(root==NULL){
		return;
	}
	pre1.push_back(root->data);
	preorder1(root->l);
	preorder1(root->r);
}
void preorder2(Node *root){  //前序遍历的逆遍历（根右左） 
	if(root==NULL){
		return;
	}
	pre2.push_back(root->data);
	preorder2(root->r);
	preorder2(root->l);
}
void postorder1(Node *root){   //后序遍历（左右根） 
	if(root==NULL){
		return;
	}
	postorder1(root->l);
	postorder1(root->r);
	post1.push_back(root->data);
}
void postorder2(Node *root){   //后序遍历的逆遍历（右左根） 
	if(root==NULL){
		return;
	}
	postorder2(root->r);
	postorder2(root->l);
	post2.push_back(root->data);
}
int main(){
	int n;
	cin>>n;
	Node *root = NULL;
	for(int i = 0;i
		int t;
		cin>>t;
		root = build(root,t);
		s.push_back(t);
	}
	preorder1(root);  //进行前序遍历 
	if(s!=pre1){   //如果不是前序遍历就进行前序遍历的逆遍历 
		preorder2(root);
		if(s!=pre2){   //如果也不是前序遍历的逆遍历就输出NO 
			cout<<"NO";
		}else{    //如果是前序遍历的逆遍历就输出YES 
			cout<<"YES"<
			postorder2(root);   //进行后序遍历的逆遍历然后输出 
			for(int i = 0;i
				cout<
				if(i!=n-1){
					cout<<" ";
				}
			}
		}
	}else{  //如果是前序遍历就输出YES 
		cout<<"YES"<
		postorder1(root);   //进行后序遍历然后输出 
		for(int i = 0;i
			cout<
			if(i!=n-1){
				cout<<" ";
			} 
		}
	}
}