LC 572. Subtree of Another Tree

标签：return LC int 572 Tree subRoot primes null root

572. Subtree of Another Tree

---

思路与题解

这是一道挺有意思的问题，有三种解法，其中第二种是KMP算法的应用。筛法的原理参见 204. Count Primes。

解法1：暴力dfs法。直接暴力扫描每个结点对应的子树结构，与待查询子树进行对比。时间复杂度 \(O(|s| \times |t|)\)。

import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public boolean dfs(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot != null) return false;
        else if (root != null && subRoot == null) return false;
        else if (root == null && subRoot == null) return true;

        if (root.val == subRoot.val) {
            return dfs(root.left, subRoot.left) && dfs(root.right, subRoot.right);
        }
        return false;
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot != null) return false;
        else if (root != null && subRoot == null) return false;
        else if (root == null && subRoot == null) return true;

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        while (stack.size() != 0 || root != null) {
            if (root == null) {
                root = stack.pop();
                root = root.right;
            } else {
                boolean res = false;
                if (root.val == subRoot.val) res = dfs(root, subRoot);
                if (res == true) return true;

                stack.push(root);
                root = root.left;
            }
        }

        return false;
    }
}

解法2：其实原理是计算每个树结点的哈希值，然后可以对比待查子树的根结点的哈希值与树的每一个结点的哈希值。重要的是哈希函数的设计，官方解答采用了这样一个哈希函数：

\[\text{hash}(n_{k}) = n_{k}.val + 31 * primes[\text{sizeOf}(n_{k}.left)] * \text{hash}(n_{k}.left) + 179 * primes[\text{sizeOf}(n_{k}.right)] * \text{hash}(n_{k}.right) \]

其中\(primes\)是素数数组，其实本质上就是应用了质数积不容易碰撞的事实。其时间复杂度取决于筛法是采用线性筛还是埃氏筛。

import java.util.HashMap;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {};
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    int mod  = 7 * 1000_000_000;

    // 使用埃氏筛求解打表，top n里大概有x/ln(n)个素数，按每10个数至少有1个素数计算
    public int[] calcPrimeTopK(int k) {
        int i = 1, n = k * 10;
        boolean[] visited = new boolean[n];
        int[] primes = new int[k];
        primes[0] = 1;

        for (int j = 2; i < k; j++) {
            if (visited[j] != true) primes[i++] = j;
            for (int jj = j; (long) jj * j < n; jj++) {
                visited[jj * j] = true;
            }
        }

        return primes;
    }

    public int[] calcTreeNodeHash(TreeNode root, HashMap<TreeNode, int[]> map, int[] primes) {
        if (root == null) return new int[] {0, 0};

        int[] left = calcTreeNodeHash(root.left, map, primes);
        int[] right = calcTreeNodeHash(root.right, map, primes);

        int[] meta = new int[2];
        meta[0] = 1 + left[0] + right[0];
        meta[1] = root.val + 3 * left[1] * primes[left[0]] % mod + 7 * right[1] * primes[right[0]] % mod;
        map.put(root, meta);

        return meta;
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot != null) return false;
        else if (root != null && subRoot == null) return false;
        else if (root == null && subRoot == null) return true;

        // 埃氏筛求解质数表
        int[] primes = calcPrimeTopK(2000);

        // 对于每一个结点计算结点哈希
        HashMap<TreeNode, int[]> treeNodeMap = new HashMap<>();
        HashMap<TreeNode, int[]> subTreeMap = new HashMap<>();

        calcTreeNodeHash(root, treeNodeMap, primes);
        calcTreeNodeHash(subRoot, subTreeMap, primes);

        // 寻找hash值相同的结点
        int target = subTreeMap.get(subRoot)[1];
        for (int[] candidate : treeNodeMap.values()) {
            if (candidate[1] == target) return true;
        }

        return false;
    }
}

References

[1] 关于从埃氏筛到线性筛你不会想知道的那些事（证明，慎入）

[2] 线性筛的理解及应用

标签：return,LC,int,572,Tree,subRoot,primes,null,root
From： https://www.cnblogs.com/GradientBoosted/p/17132929.html