L2-004 这是二叉搜索树吗？
一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，
- 其左子树中所有结点的键值小于该结点的键值；
- 其右子树中所有结点的键值大于等于该结点的键值；
- 其左右子树都是二叉搜索树。
所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。
给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。
输入格式：
输入的第一行给出正整数 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
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { static int N=1010,mod=1000000007; static double res=0; static int a[]=new int[N]; static int ans1[]=new int[N],cnt1,ans2[]=new int[N],cnt2; // static double money[]=new double[N]; //static int h[]=new int[N]; //static boolean f[]=new boolean[N];//true表示在一组 false表示在重复组 //qq public static void main(String []args) throws IOException{ //System.out.println(100); BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); String g[]=br.readLine().split(" "); int n=Integer.parseInt(g[0]); //String g[]=br.readLine().split(" "); g=br.readLine().split(" "); for (int i = 0; i < n; i++) { a[i]=Integer.parseInt(g[i]); } if(n==1){ System.out.println("YES"); System.out.println(a[0]); return; } if(check1(0,n-1)){ System.out.println("YES"); StringBuilder stringBuilder=new StringBuilder(); for (int i = 0; i <n; i++) { stringBuilder.append(ans1[i]+" "); } System.out.println(stringBuilder.toString().trim()); }else if(check2(0,n-1)){ System.out.println("YES"); StringBuilder stringBuilder=new StringBuilder(); for (int i = 0; i <n; i++) { stringBuilder.append(ans2[i]+" "); } System.out.println(stringBuilder.toString().trim()); }else{ System.out.println("NO"); } } static boolean check1(int l,int r){ if(l>r)return true;//一定要增加空树判断 if(l==r){ ans1[cnt1++]=a[l]; return true; } int root=a[l]; //判断左子树的数是不是比自己小 int i = l+1; for (; i <= r && a[i]<root; i++); int j=i; //判断右子树的数是不是比自己大或者相等 for (; i <=r && a[i]>=root; i++); if(i-1!=r)return false; //判断子树是否符合 boolean f=check1(l+1, j-1)&&check1(j, r); if(f==true)ans1[cnt1++]=root; return f; } static boolean check2(int l,int r){ if(l>r)return true; if(l==r){ ans2[cnt2++]=a[l]; return true; } int root=a[l]; //判断左子树的数是不是比自己大或者相等 int i = l+1; for (i = l+1; i <= r && a[i]>=root; i++); int j=i; //判断右子树的数是不是比自己小 for (; i <=r && a[i]<root; i++); if(i-1!=r)return false; //判断子树是否符合 boolean f=check2(l+1, j-1)&&check2(j, r); if(f==true)ans2[cnt2++]=root; return f; } }
