对于两棵彼此独立的二叉树A和B，请编写一个高效算法，检查A中是否存在一棵子树与B树的拓扑结构完全相同。
给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树。
解题思路：
1.我们可以对于A树的每一个节点，进行判断，看是否和B相等，但是这样的时间复杂度为O(M*N)，设A的节点数为M，B的节点数为N。
2.另外一种思路就是，我们先把两个树序列化，然后判断strA是否含有strB的子串，判断子串的时候，我们采用KMP算法，这样时间复杂度就可以降为O(M+N)。其中，我们需要采用前序遍历（或后序遍历），确保子树的序列化是连续的。中序遍历会由于插入中间值，导致序列化后不一致。
3.序列化的时候，我们需要对空的叶子节点进行插入特殊符号（数值）操作，这是用于判断只有一个叶子节点的节点的结构，如：
//需要加上叶子节点，加上叶子节点是为了判断当某个节点只有一个叶子节点时，能够知道是左孩子还是右孩子
//如–A—–A
//—/———-\
//–B———-B
//如树1，A的左节点为B，右节点为空
//树2，A的做节点为空，右节点为B
//如果不加叶子节点，那么前序遍历均为AB
//加上叶子节点后，分别为AB###和A#B##，可以判断
AC代码：
//需要加上叶子节点，加上叶子节点是为了判断当某个节点只有一个叶子节点时，能够知道是左孩子还是右孩子
//如 A A
// / \
// B B
//如果不加叶子节点，那么前序遍历均为AB
//加上叶子节点后，分别为AB###和A#B##，可以判断
/*
对于两棵彼此独立的二叉树A和B，请编写一个高效算法，检查A中是否存在一棵子树与B树的拓扑结构完全相同。
给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树
*/
//前序遍历+KMP
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class IdenticalTree {
public:
bool chkIdentical(TreeNode* A, TreeNode* B) {
// write code here
if (B == NULL) return true;
else if (A == NULL) return false;
vector<int> pattern;
vector<int> str;
dfs(A, str);
dfs(B, pattern);
if (str.size()<pattern.size()) return false;
//构建next数组
vector<int> next(pattern.size() + 1, 0);
for (int i = 1; i<pattern.size(); ++i)
{
int j = next[i];
while (j>0 && pattern[i] != pattern[j])
j = next[j];
if (pattern[i] == pattern[j])
next[i + 1] = j + 1;//求next[i+1]的值，所以比较的是p[i]和p[j]
}
//使用KMP
int j = 0;
for (int i = 0; i<str.size(); ++i)
{
while (j>0 && str[i] != pattern[j])
j = next[j];
if (str[i] == pattern[j])
j++;//比较下一个值
if (j == pattern.size())
{
//匹配到字串了，返回真
return true;
}
}
//没找到，false
return false;
}
//进行前序遍历
void dfs(TreeNode* root, vector<int>&preOrder)
{
if (root == NULL){
//需要加上叶子节点，加上叶子节点是为了判断当某个节点只有一个叶子节点时，能够知道是左孩子还是右孩子
//如 A A
// / \
// B B
//如果不加叶子节点，那么前序遍历均为AB
//加上叶子节点后，分别为AB###和A#B##，可以判断
preOrder.push_back(INT_MAX);
return;
}
preOrder.push_back(root->val);
dfs(root->left, preOrder);
dfs(root->right, preOrder);
}
};