判断t1树是否有与t2树拓扑结构完全相同的子树

//判断t1树是否有与t2树拓扑结构完全相同的子树
public class ContainSameSubTree{

      //二叉树结点的定义
	public static class Node{

		public int value;
		public Node left;
		public Node right;

		public Node(int data)
		{
			this.value=data;
		}
	}

       //解法一判断h1中每个子树是否有与h2相同的结构,时间复杂度为O(N*M)
	//判断是否有相同的子树结构(解法二:先序列化，然后利用字符串的kmp匹配算法,时间复杂度为O(N+M))
	public static boolean IsContainSameSubTree(Node h1,Node h2){
      
        if(h2==null)
        {
        	return true;
        }
        if(h1==null)
        {

        	return false;
        }
        String  str1=serialByPre(h1);
        String  str2=serialByPre(h2);

        return getIndexOf(str1,str2)!=-1;

	}
   //先序遍历序列化二叉树
	public static String serialByPre(Node head)
	{

        if(head==null)
        {
        	return "#!";
        }
        String res=head.value+"!";
        res+=serialByPre(head.left);
        res+=serialByPre(head.right);

        return res;

	}
    
    //字符串匹配 (KMP算法)
    public static int getIndexOf(String s,String m)
    {

    	if(s==null||m==null||m.length()<1||s.length()<m.length())
    	{
    		return -1;
    	}
    	//将字符串转换为数组
    	char[]ss=s.toCharArray();
    	char[]ms=m.toCharArray();
        
        int si=0;
        int mi=0;
        int []next=getNextArray(ms);
        while(si<ss.length&&mi<ms.length)
        {
        	if(ss[si]==ms[mi])
        	{
        		si++;
        		mi++;
        	}
        	else if(next[mi]==-1)
        	{
               si++;
        	}else{
        		mi=next[mi];
        	}
        }
        return mi==ms.length?si-mi:-1;

    }

    //获得next数组
    public static int[]getNextArray(char[]ms)
    {
       if(ms.length==1)
       {
       	return new int[]{-1};
       }
       int []next=new int[ms.length];
       next[0]=-1;
       next[1]=0;
       int pos=2;
       int cn=0;
       while(pos<next.length)
       {

       	   if(ms[pos-1]==ms[cn])
       	   {
       	   	next[pos++]=++cn;
       	   }
       	   else if(cn>0)
       	   {
       	   	cn=next[cn];
       	   }
       	   else{
       	   	next[pos++]=0;
       	   }
       }
       return next;

    }

	public static void  main(String[] args)
	{
      Node h1=new Node(1);
      h1.left=new Node(2);
      h1.right=new Node(3);
      h1.left.left=new Node(4);
      h1.left.right=new Node(5);
      h1.right.left=new Node(6);
      h1.right.right=new Node(7);
      h1.left.left.right=new Node(8);
      h1.left.right.left=new Node(9);

      Node h2=new Node(2);
      h2.left=new Node(4);
      h2.right=new Node(5);
      h2.left.right=new Node(8);
      //h2.right.left=new Node(9);


      System.out.println(IsContainSameSubTree(h1,h2));


	}
}