c++ O(n+m) Time O(n+m) Space non-recursive solution

• The key idea is to serialize the tree into a string so that any subtree in that tree will be a consecutive substring. Then the problem turns into substring finding problem. Here is the non-recursive code in case the tree is quite deep (depth > 10000) to prevent stack overflow.

``````class Solution {
public:
vector<int> preKMP(string substr) {
int m = substr.size();
vector<int> f(m);
int k;
f[0] = -1;
for (int i = 1; i < m; i++) {
k = f[i - 1];
while (k >= 0) {
if (substr[k] == substr[i - 1])
break;
else
k = f[k];
}
f[i] = k + 1;
}
return f;
}

bool KMP(string substr, string str) {
int m = substr.size();
int n = str.size();
vector<int> f;
f = preKMP(substr);
int i = 0;
int k = 0;
while (i < n) {
if (k == -1) {
i++;
k = 0;
}
else if (str[i] == substr[k]) {
i++;
k++;
if (k == m) {
return true;
}
}
else {
k = f[k];
}
}
return false;
}

string postOrderTraversal(TreeNode* root) {
string str;
stack<pair<TreeNode*, int>> s;
s.push(pair<TreeNode*, int>(root, 0));
while (!s.empty()) {
pair<TreeNode*, int> p = s.top();
TreeNode* node = p.first;
int idx = p.second;
if (node == NULL) {
s.pop();
continue;
}
if (idx == 0) {
str.push_back('(');
s.top().second++;
s.push(pair<TreeNode*, int>(node->left, 0));
} else if (idx == 1) {
s.top().second++;
s.push(pair<TreeNode*, int>(node->right, 0));
} else {
str += to_string(node->val);
str.push_back(')');
s.pop();
}
}
return str;
}

bool isSubtree(TreeNode* s, TreeNode* t) {
string post_t = postOrderTraversal(t);
string post_s = postOrderTraversal(s);
//int pos = post_s.find(post_t);
//return (pos != string::npos);
return KMP(post_t, post_s);
}
};
``````

• What makes you think `find` is linear time? I checked cppreference.com which doesn't talk about its complexity and cplusplus.com which says this:

Complexity
Unspecified, but generally up to linear in length()-pos times the length of the sequence to match (worst case).

Times, not plus.

• @StefanPochmann You are right! I didn't check the complexity of find function. To get a truely linear time algorithm, we have to use KMP in my case here. I already upload the code. Thank you for the question!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.