Java描述 LeetCode，572. 另一棵树的子树，欧拉筛选法

𝑰’𝒎 𝒉𝒉𝒈, 𝑰 𝒂𝒎 𝒂 𝒈𝒓𝒂𝒅𝒖𝒂𝒕𝒆 𝒔𝒕𝒖𝒅𝒆𝒏𝒕 𝒇𝒓𝒐𝒎 𝑵𝒂𝒏𝒋𝒊𝒏𝒈, 𝑪𝒉𝒊𝒏𝒂.

• 🏫 𝑺𝒉𝒄𝒐𝒐𝒍: 𝑯𝒐𝒉𝒂𝒊 𝑼𝒏𝒊𝒗𝒆𝒓𝒔𝒊𝒕𝒚
• 🌱 𝑳𝒆𝒂𝒓𝒏𝒊𝒏𝒈: 𝑰’𝒎 𝒄𝒖𝒓𝒓𝒆𝒏𝒕𝒍𝒚 𝒍𝒆𝒂𝒓𝒏𝒊𝒏𝒈 𝒅𝒆𝒔𝒊𝒈𝒏 𝒑𝒂𝒕𝒕𝒆𝒓𝒏, 𝑳𝒆𝒆𝒕𝒄𝒐𝒅𝒆, 𝒅𝒊𝒔𝒕𝒓𝒊𝒃𝒖𝒕𝒆𝒅 𝒔𝒚𝒔𝒕𝒆𝒎, 𝒎𝒊𝒅𝒅𝒍𝒆𝒘𝒂𝒓𝒆 𝒂𝒏𝒅 𝒔𝒐 𝒐𝒏.
• 💓 𝑯𝒐𝒘 𝒕𝒐 𝒓𝒆𝒂𝒄𝒉 𝒎𝒆：𝑽𝑿
• 📚 𝑴𝒚 𝒃𝒍𝒐𝒈: 𝒉𝒕𝒕𝒑𝒔://𝒉𝒉𝒈𝒚𝒚𝒅𝒔.𝒃𝒍𝒐𝒈.𝒄𝒔𝒅𝒏.𝒏𝒆𝒕/
• 💼 𝑷𝒓𝒐𝒇𝒆𝒔𝒔𝒊𝒐𝒏𝒂𝒍 𝒔𝒌𝒊𝒍𝒍𝒔：𝒎𝒚 𝒅𝒓𝒆𝒂𝒎
  

1-1：暴力解

核心思路就是每遍历一个Root节点就和SubRoot进行树与树之间的比较，比较容易想到，代码如下：

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (root == null) {
        return false;
    }
    return check(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

public boolean check(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
        return true;
    }
    if (p == null || q == null || p.val != q.val) {
        return false;
    }
    return check(p.left, q.left) && check(p.right, q.right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1-2：串匹配

核心思路就是像官方题解里面的那样。

• 用一个序列代表一个树的结构，然后通过序列之间的匹配来确定是否包含这个子树。
• 前序遍历并不能唯一确定一个树的结构，所以他提出了，遇见空节点就插入空节点的做法，从而保证唯一性。

他用的是KMP的做法，我用的是String，因为String正好有contains这个方法可以用起来，因为主要考察的是思路吧，这个串匹配应该不是重点。代码如下：

public static void getString(TreeNode root, StringBuilder r) {
    if (root == null) {
        return;
    }
    r.append(root.val).append(",");
    if (root.left != null) {
        getString(root.left, r);
    } else {
        r.append("n,");
    }
    if (root.right != null) {
        getString(root.right, r);
    } else {
        r.append("n,");
    }
}

public static boolean isSubtree2(TreeNode root, TreeNode subRoot) {
    StringBuilder r = new StringBuilder(), s = new StringBuilder();
    getString(root, r);
    getString(subRoot, s);
    return r.toString().contains(s.toString());
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

要注意这里为什么加”，“，因为比如12n和2n，两个单节点的树，从string上看这里12.contains(2)是true，但事实上，并不是子树，所以要特别挑出这一点。

1-3：绝绝子，树hash

这个比较牛，首先得会欧拉筛选法，我也没听说过，于是我找了一个学习视频，几分钟学习了下核心思想：B站视频

核心思想如下：
两个数组

• sifted[i] 代表第i个数字是否被筛掉了，筛掉的意思就是说这个数不是素数。
• prime[i]代表第i+1个素数。

主角一共有两个x和y，x代表从2开始的没有被筛掉的自然数，y代表prime[i]，也就是素数数组。
首先，x=2，从sifted数组中查看2这个数字有没有被筛掉，sifited[x]是false，意思就是没有被筛掉，作为素数加入到prime[]数组中。

y从prime[0]开始，也就是从第一个素数开始检查，看x是否能整除y。

• 不能整除，筛掉x*y，也就是sifted[x*y]=true，继续检查下一个y值，prime[1]。。。
• 如果能整除，退出循环。检查下一个x,x=3。
  如此反复。具体代码如下：

    public static int[] oula(int n) {
        boolean[] sifted = new boolean[n + 1]; // 代表1～n个数字 true代表被筛掉了，false代表没有被筛掉
        int[] prime = new int[n]; // 素数数组
        int point = 0; // 素数的指针
        for (int x = 2; x <= n; x++) {
            if (!sifted[x]) { // 如果没有被筛掉
                prime[point++] = x;
            }
            for (int j = 0; j <= point; j++) { // 遍历素数数组，通过y值进行筛选，被筛选掉的要做记录，退出条件是x能整除y<=>x%y==0
                int y = prime[j];
                if (x * y > n) { // 当x*y是，比n大的数，没必要筛选，因为不在考虑范围之内。
                    break;
                }
                sifted[y * x] = true;
                if (x % y == 0) {
                    break;
                }
            }
        }
        return prime;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

但是，这个里面并没有解释为什么要用素数哈，我的理解是素数之间做乘积运算，对hash值的碰撞比较少，也就是出现重复hash值的情况会降低。

之后再按照公式那么计算就好了，计算的时候，还需要再对代码进行理解一下：

public boolean isSubtree3(TreeNode root, TreeNode subRoot) {
    int n = 100000;
    int[] prime = oula(n);
    int mode = 70000;
    Map<TreeNode, int[]> rootMap = new HashMap<>();
    Map<TreeNode, int[]> subRootMap = new HashMap<>();
    dfs(root, rootMap, prime, mode);
    dfs(subRoot, subRootMap, prime, mode);
    int subRootHash = subRootMap.get(subRoot)[0];
    for (Map.Entry<TreeNode, int[]> entry : rootMap.entrySet()) {
        if (entry.getValue()[0] == subRootHash) {
            return true;
        }
    }
    return false;
}
public void dfs(TreeNode node, Map<TreeNode, int[]> map, int[] prime, int mod) {
    if (node == null) {
        return;
    }
    map.put(node, new int[]{node.val, 1});
    dfs(node.left, map, prime, mod);
    dfs(node.right, map, prime, mod);
    if (node.left != null) {
        int[] val = map.get(node);
        val[1] += map.get(node.left)[1];
        val[0] = (int) (val[0] + 31L * map.get(node.left)[0] * prime[map.get(node.left)[1]]) % mod;
    }
    if (node.right != null) {
        int[] val = map.get(node);
        val[1] += map.get(node.right)[1];
        val[0] = (int) (val[0] + 179L * map.get(node.right)[0] * prime[map.get(node.right)[1]]) % mod;
    }
}
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

• map的key是一个int[] ，因为int[0]代表子树映射公式计算的值，int[1]代表这个子树的个数。
• 在实现的时候，对着公式要好好看看，很容易把对应的值弄错。

其他，照着官方详解看，应该没有什么太大的压力了。主要收获就是这里的求素数的方法，以后再做素数的时候，不要再用传统的1~ $\sqrt[]{n}$，挨个判断的做法了。