LeetCode - Subtree of Another Tree - C++

Let's discuss ⬇️

[@lansicus]

// O(M*N) time complexity
class Solution {
private:
bool isSameTree(TreeNode *p, TreeNode *q) {
if (!p && !q) { return true; }
if (!p || !q) { return false; }
if (p->val == q->val && isSameTree(p->left, q->left)
&& isSameTree(p->right, q->right)) {
return true;
}
return false;
}
public:
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if (!root) { return false; }
if (isSameTree(root, subRoot)) { return true; }
if (isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot)) {
return true;
}
return false;
}
};

[@lansicus]

// my attempty at O(m+n) time complexity w/ basic serialization and advanced kmp matching to get O(m+n) time complexity for finding substring
// ***note that time complexity may be inaccurate***
class Solution {
private:
bool kmpSearch(const string &s1, const string &s2) {
vector lps = getlps(s2);
int j = 0;
for (int i = 0; i < s1.length(); ++i) {
while (j > 0 && s1[i] != s2[j]) { j = lps[j - 1]; }
if (s1[i] == s2[j]) { j++; }
if (j == s2.length()) { return true; }
}
return false;
}
vector getlps(const string &s) {
vector lps(s.length());
int j = 0;
for (int i = 1; i < s.length(); ++i) {
while (j > 0 && s[j] != s[i]) { j = lps[j - 1]; }
if (s[j] == s[i]) { lps[i] = ++j; }
}
return lps;
}
void serialize(TreeNode *tn, string &s) {
if (!tn) { s.append(",#"); }
else {
s.append(",");
s.append(to_string(tn->val));
serialize(tn->left, s);
serialize(tn->right, s);
}
}
public:
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
string root_s, subRoot_s;
serialize(root, root_s);
serialize(subRoot, subRoot_s);
return kmpSearch(root_s, subRoot_s);
}
};