1、是否存在拓扑结构相同子树

题目描述：对于两棵彼此独立的二叉树A和B，请编写一个高效算法，
检查A中是否存在一棵子树与B树的拓扑结构完全相同。
给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树。
思路：把两棵树都序列化成字符串，然后用kmp字符喘匹配算法查找B树的序列化字符串是否A树的子串
题目描述：对于两棵彼此独立的二叉树A和B，请编写一个高效算法，
检查A中是否存在一棵子树与B树的拓扑结构完全相同。
给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树。
思路：把两棵树都序列化成字符串，然后用kmp字符喘匹配算法查找B树的序列化字符串是否A树的子串

  public boolean chkIdentical(TreeNode A, TreeNode B) {
                    // write code here
                        StringBuilder a=new StringBuilder();
                        StringBuilder b=new StringBuilder();

                        getTreeString(A, a);
                        getTreeString(B,b);
                        int[] next=new int[b.length()];
                        getNextArray(b.toString().toCharArray(), next);
                        return kmpSearch(a.toString().toCharArray(), b.toString().toCharArray(), next);
                }

                public void getTreeString(TreeNode node,StringBuilder s){
                        if(node==null){
                                    s.append("#");
                                    return;
                        }
                        s.append(node.val+"!");
                        getTreeString(node.left, s);               
                        getTreeString(node.right, s);

                }
   public boolean kmpSearch(char[] s,char[] p,int[] next){
                           int i=0,j=0;
                           while(i<s.length&&j<p.length){
                                       if(j==-1||s[i]==p[j]){
                                                   j++;
                                                   i++;
                                       }else{
                                                   j=next[j];
                                       }
                           }
                           if(j==p.length){
                                       return true;
                           }else{
                                       return false;
                           }
               }
               public void getNextArray(char[] p,int[] next){
                           int k=-1;
                           int i=0;
                           next[0]=-1;
                           while(i<p.length-1){
                                       if(k==-1||p[k]==p[i]){
                                                   i++;
                                                   k++;
                                                   if(p[i]!=p[k]){
                                                               next[i]=k;
                                                   }else{
                                                               next[i]=next[k];
                                                   }
                                       }else{
                                                   k=next[k];
                                       }
                           }
               }