652.寻找重复的子树

链接：652.寻找重复的子树
难度：Medium
标签：树、深度优先搜索、哈希表、二叉树
简介：给定一棵二叉树 root，返回所有重复的子树。

题解 1 - cpp

• 编辑时间：2022-09-05
• 执行用时：52ms
• 内存消耗：53.7MB
• 编程语言：cpp
• 解法介绍：map 存储相同节点·。

class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        unordered_map<string, vector<TreeNode*>> m;
        dfs(m, root);
        vector<TreeNode *> ans;
        for (auto &item : m) {
            if (item.second.size() > 1) {
                ans.push_back(item.second[0]);
            }
        }
        return ans;
    }
    string dfs(unordered_map<string, vector<TreeNode*>> &m, TreeNode *root) {
        if (!root) return "";
        string s = "(" + to_string(root->val) + ",[" + dfs(m, root->left) + "],[" + dfs(m, root->right) + "])";
        m[s].push_back(root);
        return s;
    }
};