算法编程题-判断一颗树中是否有与另一棵树拓扑结构完全相同的子树

题目：

普通解法：二叉树遍历+匹配

时间复杂度O(N*M)

N：代表t1节点数   M：代表t2节点数

最优解法为二叉树序列化+KMP算法

时间复杂度O（M+N）

二叉树t1序列化  -> 字符串str1

二叉树t2序列化  -> 字符串str2

KMP算法判断str1中是否含有str2

如果str1包含str2，说明t1某棵子树于t2一致，否则t1中没有任何一颗子树与t2一致

实例代码如下：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class IdenticalTree {
public:
//先序遍历将二叉树序列化
 string serial(TreeNode *root)
{
	string str;
	TreeNode *p = root;
	stack<TreeNode*> sk;
	
	while (p || !sk.empty())
	{
		while (p)
		{
			sk.push(p);
			str = str+to_string(p->val)+'!';
			p = p->left;
		}
		if (nullptr == p)
			str += "#!";
		p = sk.top();
		sk.pop();
		p = p->right;
	}
	str += "#!";
	return str;
}
    
    bool chkIdentical(TreeNode* A, TreeNode* B) {
        // write code here
        if(NULL == A || NULL == B)
            return false;
        string strA = serial(A);
        string strB = serial(B);
      //判断序列化后两者的包含关系，若A包含B，则满足题意
       string::size_type idx = strA.find(strB);
        return (idx == string::npos) ? false:true;
    }
};