在这里给出两种做法，
第一种是直接搜索，O(n * m) 的worse case,
class Solution {
public:
bool isSameTree(TreeNode* x, TreeNode* y){
if(x == NULL && y == NULL) return true;
else if(x == NULL || y == NULL) return false;
if(x->val != y->val) return false;
return isSameTree(x->left, y->left) && isSameTree(x->right, y->right);
}
bool isSubtree(TreeNode* s, TreeNode* t) {
if(s == NULL && t == NULL) return true;
else if(s == NULL || t == NULL) return false;
if(isSameTree(s, t)) return true;
return isSubtree(s->left, t) || isSubtree(s->right, t);
}
};
第二种参考网上的思路，把树转化成string，然后再用find substring的办法。不过库函数的find substring一般也不用kmp，而是直接一个一个的搜索查找，所以复杂度也是 O(n * m) 级别. 两种方法leetcode runtime差不多
class Solution {
public:
void serialize(TreeNode* root, string &s){
if(root){
s += '(' + to_string(root->val) + ')';
s += ' ';
serialize(root->left, s);
serialize(root->right, s);
}else{
s += '#' + ' ';
}
}
bool isSubtree(TreeNode* s, TreeNode* t) {
if(!s && !t) return true;
else if(!s || !t) return false;
string s_string, t_string;
serialize(s, s_string);
serialize(t, t_string);
return s_string.find(t_string) != string::npos;
}
};
