Mind palace

some thoughts

0%

572. Subtree of Another Tree

Posted on Edited on In Disqus:
Symbols count in article: 2.4k Reading time ≈ 2 mins.

O(m+n) time O(m+n) space
前序遍历拼唯一可能的字符串再跑rolling hash版的字符串查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        dfs(s, ss);
        dfs(t, st);
        return find(ss, st) != -1;
    }

    void dfs(TreeNode *p, string &s) { // 前序遍历拼字符串
        if (!p) {
            s += " #";
            return;
        }
        s += " " + to_string(p->val);
        dfs(p->left, s);
        dfs(p->right, s);
    }

    string ss, st;

    int find(const string &haystack, const string &needle) {
        int h = haystack.length(), n = needle.length();
        long M = INT_MAX, B = 256; // INT_MAX是质数！
        if (h < n) return -1;
        long highest_power = 1, hh = 0, nh = 0;
        for (int i = 0; i < n; ++i) {
            highest_power = (highest_power * B) % M;
            nh = (nh * B + needle[i]) % M;
            hh = (hh * B + haystack[i]) % M;
        }
        for (int i = 0; i < h - n + 1; ++i) {
            if (i >= 1) {
                hh = (hh * B + M - haystack[i - 1] * highest_power % M + haystack[i + n - 1]) % M; // 这里highest_power是B的n次方，因为先整体左移再减高位，如果先减高位再整体左移就是n-1次方了
            }
            if (hh == nh && haystack.substr(i, n) == needle) {
                return i;
            }
        }
        return -1;
    }
};

O(m2+n2+mn) time考虑到字符串拼接也要花时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        return preorder(s).find(preorder(t)) != string::npos;
    }

    string preorder(TreeNode *root) {
        return " " + (root ? to_string(root->val) + preorder(root->left) + preorder(root->right) : "#");
    }
};

O(mn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if (!s && t) return false; // 防止s为空导致segv
        return isSame(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t);
    }

    bool isSame(TreeNode *s, TreeNode *t) {
        if (!s && !t) return true;
        if (!s || !t) return false;
        return s->val == t->val && isSame(s->left, t->left) && isSame(s->right, t->right);
    }
};