一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，
其左子树中所有结点的键值小于该结点的键值； 其右子树中所有结点的键值大于等于该结点的键值； 其左右子树都是二叉搜索树。所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。
给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。
输入格式：
输入的第一行给出正整数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<iostream> #include<cstdio> #include<vector> using namespace std; struct node{ int num; struct node* left; struct node* right; }; struct node* insert(struct node * root,int n){ if(root==NULL){ root=new node(); root->left=NULL; root->right=NULL; root->num=n; } else if(root->num>n){ root->left=insert(root->left,n); }else if(root->num<=n){ root->right=insert(root->right,n); } return root; } vector<int>res1,res2,res3; void preorder1(struct node* root){ if(root==NULL)return; res1.push_back(root->num); preorder1(root->left); preorder1(root->right); } void preorder2(struct node* root){ if(root==NULL)return; res2.push_back(root->num); preorder2(root->right); preorder2(root->left); } vector<int>res4; void hostorder(struct node* root){ if(root==NULL)return; hostorder(root->left); hostorder(root->right); res4.push_back(root->num); } void hostorder2(struct node* root){ if(root==NULL)return; hostorder2(root->right); hostorder2(root->left); res4.push_back(root->num); } int main(){ int n; scanf("%d",&n); struct node* root=NULL; for(int i=0;i<n;i++){ int num; scanf("%d",&num); res3.push_back(num); root=insert(root,num); } preorder1(root); preorder2(root); bool flag=false; int i; for(i=0;i<res1.size();i++){ if(res1[i]!=res3[i]){ break; } } if(i==res1.size()){ printf("YES\n"); hostorder(root); for(int j=0;j<res4.size()-1;j++){ printf("%d ",res4[j]); } printf("%d\n",res4[res4.size()-1]); return 0; } for(i=0;i<res2.size();i++){ if(res2[i]!=res3[i]){ break; } } if(i==res2.size()){ printf("YES\n"); hostorder2(root); for(int j=0;j<res4.size()-1;j++){ printf("%d ",res4[j]); } printf("%d\n",res4[res4.size()-1]); return 0; } printf("NO\n"); return 0; }