一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，
其左子树中所有结点的键值小于该结点的键值；其右子树中所有结点的键值大于等于该结点的键值；其左右子树都是二叉搜索树。所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。
给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。
输入格式：
输入的第一行给出正整数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<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<string> #define LL long long #define inf 0x3f3f3f3f const int maxn=100001; using namespace std; int a[maxn],t; bool f(int l,int r,int k)///遍历 { if(l>=r) return true;///数组出界 int s=a[l],i; bool p,q; for(i=l+1; i<=r+1; i++) { p=q=true; for(int j=i; j<=r; j++)///左子树 if(k?s>a[j]:s<=a[j]) {p=false; break;} for(int j=i-1; j>l; j--)///右子树 { if(k?s<=a[j]:s>a[j]) {q=false; break;} } if(q&&p) break; } if(p&&q) return f(l+1,i-1,k)&&f(i,r,k);///进一步遍历左右子树 else return false; } void shuchu(int l,int r,int k) { if(l>r) return; if(l==r) {printf(++t==1 ? "%d" :" %d",a[l]); return;} int s=a[l],i; bool p,q; for(i=l+1; i<=r+1; i++) { p=q=true; for(int j=i; j<=r; j++)///左子树 if(k?s>a[j]:s<=a[j]) {p=false; break;} for(int j=i-1; j>l; j--)///右子树 if(k?s<=a[j]:s>a[j]) {q=false; break;} if(q&&p) break; } shuchu(l+1,i-1,k); shuchu(i,r,k); printf(++t==1 ? "%d" :" %d",s); } int main() { int n; scanf("%d",&n); for(int i=0; i<n; i++) scanf("%d",&a[i]); int t=0; if(f(0,n-1,1)){ printf("YES\n"); shuchu(0,n-1,1); } else if(f(0,n-1,0)){ printf("YES\n"); shuchu(0,n-1,0); } else printf("NO"); printf("\n"); return 0; }