572. 另一棵树的子树 解法一、暴力遍历每一个子树，比较子树是否相同 时复：O(s * t)

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
/**
 * 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 judge(TreeNode *t1, TreeNode *t2) {
   
        if(t1->val != t2->val) return false;
        if(bool(t1->left) ^ bool(t2->left)) return false;
        if(bool(t1->right) ^ bool(t2->right)) return false;
        if(t1->left && !judge(t1->left, t2->left)) return false;
        if(t1->right && !judge(t1->right, t2->right)) return false;
        return true;
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
   
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
   
            TreeNode *u = q.front();
            q.pop();
            if(judge(u, subRoot)) return true;
            if(u->left) q.push(u->left);
            if(u->right) q.push(u->right);
        }
        return false;
    }
};

解法二、 解出两颗子树的所有前序序列，若t2是t1的子树，则t2的前序序列应为t1的前序序列的子串，利用kmp算法匹配即可，代码中lNull为左子树空的标志，rNull为右子树空的标志 时复：O(s + t)

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
 * 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:
    int lNull, rNull;
    int ne[4100];
    void dfs(TreeNode* root, vector<int> &ve) {
   
        if(!root) return ;
        ve.push_back(root->val);
        if(root->left) dfs(root->left, ve);
        else ve.push_back(lNull);
        if(root->right) dfs(root->right, ve);
        else ve.push_back(rNull);
    }
    void get_next(vector<int> v1){
   
        int i = 0, j = -1;  //这里j是初始化为-1！
        int len = v1.size();
        ne[0] = -1;
        while(i < len){
   
            if(j == -1 || v1[i] == v1[j]){
   
                ++ i; ++ j;
                ne[i] = j;
            }
            else j = ne[j];
        }
    }
    bool kmp(vector<int> &v1, vector<int> &v2) {
   
        int len1 = v1.size(), len2 = v2.size();
        int i = 0, j = 0, cnt = 0;
        while(i < len2){
   
            if(j == -1 || v1[j] == v2[i]){
   
                ++ i; ++ j;
            }
            else j = ne[j];
            if(j == len1) {
   
                cnt ++;  // 匹配到
            }
        }
        return cnt;
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
   
        lNull = 10001, rNull = 10002;
        vector<int> v1, v2;
        dfs(root, v2);
        dfs(subRoot, v1);
        get_next(v1);
        return kmp(v1, v2);
    }
};

解法三、 官方题解给出的哈希做法，感觉很秒