L2-004 这是二叉搜索树吗？

L2-004 这是二叉搜索树吗一棵二叉搜索树可被递归地定义为具有下列性质的二叉树对于任一结点其左子树中所有结点的键值小于该结点的键值其右子树中所有结点的键值大于等于该结点的键值其左右子树都是二叉搜索树。所谓二叉搜索树的“镜像”即将所有结点的左右子树对换位置后所得到的树。给定一个整数键值序列现请你编写程序判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。输入格式输入的第一行给出正整数 N≤1000。随后一行给出 N 个整数键值其间以空格分隔。输出格式如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果则首先在一行中输出YES然后在下一行输出该树后序遍历的结果。数字间有 1 个空格一行的首尾不得有多余空格。若答案是否则输出NO。输入样例 178 6 5 7 10 8 11输出样例 1YES5 7 6 8 11 10 8输入样例 278 10 11 8 6 7 5输出样例 2YES11 8 10 7 5 6 8输入样例 378 6 8 5 10 9 11输出样例 3NOimport java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { static int N1010,mod1000000007; static double res0; 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 brnew BufferedReader(new InputStreamReader(System.in)); BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); String g[]br.readLine().split( ); int nInteger.parseInt(g[0]); //String g[]br.readLine().split( ); gbr.readLine().split( ); for (int i 0; i n; i) { a[i]Integer.parseInt(g[i]); } if(n1){ System.out.println(YES); System.out.println(a[0]); return; } if(check1(0,n-1)){ System.out.println(YES); StringBuilder stringBuildernew 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 stringBuildernew 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(lr)return true;//一定要增加空树判断 if(lr){ ans1[cnt1]a[l]; return true; } int roota[l]; //判断左子树的数是不是比自己小 int i l1; for (; i r a[i]root; i); int ji; //判断右子树的数是不是比自己大或者相等 for (; i r a[i]root; i); if(i-1!r)return false; //判断子树是否符合 boolean fcheck1(l1, j-1)check1(j, r); if(ftrue)ans1[cnt1]root; return f; } static boolean check2(int l,int r){ if(lr)return true; if(lr){ ans2[cnt2]a[l]; return true; } int roota[l]; //判断左子树的数是不是比自己大或者相等 int i l1; for (i l1; i r a[i]root; i); int ji; //判断右子树的数是不是比自己小 for (; i r a[i]root; i); if(i-1!r)return false; //判断子树是否符合 boolean fcheck2(l1, j-1)check2(j, r); if(ftrue)ans2[cnt2]root; return f; } }