【哈希表, DFS, 二叉树】寻找重复的子树

题目

652. 寻找重复的子树

---

给定一棵二叉树 root，返回所有重复的子树。

对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

如果两棵树具有相同的结构和相同的结点值，则它们是重复的。

示例 1：

输入：root = [1,2,3,4,null,2,4,null,null,4]
输出：[[2,4],[4]]

示例 2：

输入：root = [2,1,1]
输出：[[1]]

示例 3：

输入：root = [2,2,2,3,null,3,null]
输出：[[2,3],[3]]

提示：

• 树中的结点数在[1,10^4]范围内。
• -200 <= Node.val <= 200

解题

方法一：序列化二叉树(前序遍历) 哈希表

思路

要找出具有相同的结构和相同的结点值的两棵树，那么拿出两个节点分别递归对比的方式就不现实了。

应该要做的是把树处理成一种同时记录结构与值的独一无二的形式然后放入哈希表中进行计数，如果计数等于二，就把该树的根节点放入答案列表中。

这种形式就是二叉树的序列化，我们可以边前序遍历二叉树边序列化每一棵子树，并把序列化生成的字符串在哈希表中进行计数，如果计数正好等于 2 就把当前遍历到的节点加入答案列表中。

序列化可参考：【队列, DFS, 二叉树】二叉树的序列化与反序列化

注意：

• 答案可以以任意顺序返回(题目中没提但是可以)。
• 之所以需要用哈希表计数到 2 而不是用集合判断是否存在是因为如果一个子树重复了两次以上那么用集合就会出现重复答案，而这是不被允许的。

代码

class Solution {
    Map<String, Integer> map = new HashMap<>();
    List<TreeNode> ans = new ArrayList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        dfs(root);
        return ans;
    }

    String dfs(TreeNode node) {
        if (node == null) return "";
        String s = String.valueOf(node.val) + "," +
            dfs(node.left) + "," + dfs(node.right);
        int cnt = map.getOrDefault(s, 0);
        map.put(s, ++cnt);
        if (cnt == 2) ans.add(node);
        return s;
    }
}

class Solution {
    unordered_map<string, int> mp;
    vector<TreeNode*> ans;

    string dfs(TreeNode* node) {
        if (!node) return "n";
        string s = to_string(node->val) + "," + dfs(node->left) +
            "," + dfs(node->right);
        if (++mp[s] == 2) ans.push_back(node);
        return s;
    }

public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        dfs(root);
        return ans;
    }
};