（学习资料里面的一道题）

题目

对于两棵彼此独立的二叉树A和B，请编写一个高效算法，检查A中是否存在一棵子树与B树的拓扑结构完全相同。

给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树。

分析：这是一道二叉树相关的练习题，看了老师说的，其实也很简单，这里也就设计到两个方面的知识：二叉树的序列化，KMP算法。。。咋一看可能不清楚为什么需要这两个知识，从头分析，需要判断A树中是否存在B的子树，我们可以把树进行一个前序遍历（图片左边的树为A树，右边的树为B树）：A：12453 B：245，我们可以发现A中有245字串和B中的子串相等，发现了这个东西后，再仔细思考是否可以把两个树的子树问题变换为字符串匹配的问题呢，答案是肯定的！但这里还有一个问题，你怎么知道B中的2是一个节点，4是一个节点，5是一个节点的？（举例，A中也这么理解就对了）而不是24是一个节点或者5是一个节点呢？，所以在这样的情况下我们就用到了树的序列化！（比如A树可以使用前序遍历序列化为1！2！4！#！#！5！#！#！3！#！#！ 其中！号为分隔符，#号代表空，树的序列化和反序列化不多介绍，看我的代码，或者查资料很快就能理解）
序列化的问题解决，那么问题就很简单了，直接判断A树序列化后的串是否包含B树序列化串，但如何高效呢？ 可以采用KMP算法！，这里的KMP算法我参考了tusroy的代码，我把他的gitHub地址帖在这里：

这是gitHub
http://github.com/mission-peace/interview/wiki
这是KMP算法的地址
https://github.com/missionpeace/interview/blob/master/src/com/interview/string/SubstringSearch.java

java代码实现

下面是我写得java代码，其中的KMP算法参考了大神的代码。

package com.gcp.www;

import java.util.LinkedList;
import java.util.Queue;

public class IdenticalTree {
    


    public class TreeNode {
    
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public boolean chkIdentical(TreeNode A, TreeNode B) {
    // write code here
        //序列化两个树结构
        String aTree = BinaryTreeSerializable(A);
        String bTree = BinaryTreeSerializable(B);

        //判断a树中是否存在B树序列化后的字符串(KMP算法)
        boolean result = KMP(aTree.toCharArray(),bTree.toCharArray());

        return result;
    }

    //二叉树的序列化操作（先序遍历）
    public String BinaryTreeSerializable(TreeNode root){

        if(root == null){
            return "#!";
        }
        StringBuffer sb = new StringBuffer(root.val + "!");
        sb.append(BinaryTreeSerializable(root.left));//
        sb.append(BinaryTreeSerializable(root.right));//
        return sb.toString();
    }
    //二叉树的反序列化操作
    public TreeNode BinaryTreeDeSerializable(Queue<String> bst){
        String val = bst.poll();
        if(val.equals("#")){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(val));
        root.left = BinaryTreeDeSerializable(bst);
        root.right = BinaryTreeDeSerializable(bst);
        return root;
    }

     /**
     * KMP algorithm of pattern matching.
     */
    public boolean KMP(char[] text,char[] pattern){

        int[] lps = computeTemporaryArray(pattern);
        int i = 0;
        int j = 0;
        while(i < text.length && j < pattern.length){
            if(text[i] == pattern[j]){
                i++;
                j++;
            }else{

                if(j != 0){
                    j = lps[j-1];
                }else{
                    i++;
                }
            }
        }
        if(j == pattern.length){
            return true;
        }
        return false;
    }

    /**
     *
     * Compute temporary array to maintain size of suffix which is same as prefix
     * Time/space complexity is O(size of pattern)
     */
    private int[] computeTemporaryArray(char[] pattern){
        int[] lps = new int[pattern.length];
        int index = 0;
        for(int i = 1; i < pattern.length;){
            if(pattern[index] == pattern[i]){
                lps[i] = index+1;
                i++;
                index++;
            }else{
                if(index == 0){
                    lps[i] = 0;
                    i++;
                }else{
                    index = lps[index-1];
                }
            }
        }
        return lps;
    }

    public static void main(String[] args){
        IdenticalTree test = new IdenticalTree();
        boolean result = test.KMP("123456".toCharArray(),"346".toCharArray());
        System.out.println(result);

    }
}