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


  • 1
    A

    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);
        }
    };
    

  • 2

    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.


  • 0
    A

    @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!


Log in to reply
 

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