树的同构 Java

编程语言：Java
题目：

题解：终于写出来了，成就感满满，解释见注解。
结果：AC

importjava.io.*;importjava.util.Scanner;publicclassMain{staticStreamTokenizer in=newStreamTokenizer(newBufferedReader(newInputStreamReader(System.in)));staticPrintWriter out=newPrintWriter(newOutputStreamWriter(System.out));staticScanner sc=newScanner(newBufferedInputStream(System.in));static node[] a,b;publicstaticvoidmain(String[] args)throwsIOException{int n=sc.nextInt();
        a=new node[n];
        sc.nextLine();for(int i=0;i<n;i++){String[] str=sc.nextLine().split(" ");
            a[i]=newnode(str[0],str[1],str[2]);}int m=sc.nextInt();
        b=new node[m];
        sc.nextLine();for(int i=0;i<m;i++){String[] str=sc.nextLine().split(" ");
            b[i]=newnode(str[0],str[1],str[2]);}if(n!=m)//两者长度不一致，肯定No
            out.println("No");elseif(n==0)//两者均为空树，肯定Yes
            out.println("Yes");else{int x=find(a,"A");if(x<0)//第一棵树中没有根结点，肯定No
                out.println("No");else{int y=find(b,a[x].data);if(y<0)//第二棵树中没有相同结点，肯定No
                    out.println("No");else{//两棵树都找好根结点了，开始遍历if(search(a[x],b[y]))
                        out.println("Yes");else
                        out.println("No");}}}
        out.flush();}//在传入数组中，找到数据为data的结点的下标并返回privatestaticintfind(node[] arr,String data){for(int i=0;i<arr.length;i++){if(arr[i].data.equals(data))return i;}return-1;}privatestaticbooleansearch(node x,node y){//写的很通俗易懂，自己看吧if(x.data.equals(y.data)){boolean flag1=false;boolean flag2=false;if(x.left.equals("-")){if(y.right.equals("-")){if(x.right.equals("-")&&y.left.equals("-"))returntrue;elseif(!x.right.equals("-")&&!y.left.equals("-"))returnsearch(a[Integer.parseInt(x.right)],b[Integer.parseInt(y.left)]);}elseif(y.left.equals("-")){if(!x.right.equals("-"))returnsearch(a[Integer.parseInt(x.right)],b[Integer.parseInt(y.right)]);}else{returnfalse;}}else{if(y.right.equals("-")){if(!x.right.equals("-"))returnfalse;elsereturnsearch(a[Integer.parseInt(x.left)],b[Integer.parseInt(y.left)]);}elseif(y.left.equals("-")){if(!x.right.equals("-"))returnfalse;elsereturnsearch(a[Integer.parseInt(x.left)],b[Integer.parseInt(y.right)]);}else{
                    flag1=search(a[Integer.parseInt(x.left)],b[Integer.parseInt(y.right)])&&search(a[Integer.parseInt(x.right)],b[Integer.parseInt(y.left)]);
                    flag2=search(a[Integer.parseInt(x.left)],b[Integer.parseInt(y.left)])&&search(a[Integer.parseInt(x.right)],b[Integer.parseInt(y.right)]);return flag1||flag2;}}}returnfalse;}}class node{String data;String left;String right;publicnode(String data,String left,String right){this.data=data;this.left= left;this.right= right;}}