JZTXT

LeetCode 652. 寻找重复的子树

发布时间 2023-05-28 14:54:00作者: 穿过雾的阴霾
class Solution {
public:
    vector<TreeNode*> res;
    unordered_map<string,int> hashmap;//记录每一个子树出现的次数
    string dfs(TreeNode* root)
    {
        if(!root)   return "";
        string str="";
        str+=to_string(root->val)+',';
        str+=dfs(root->left)+',';
        str+=dfs(root->right)+',';
        hashmap[str]++;
        if(hashmap[str]==2)//防止同一种子树重复计算
            res.push_back(root);
        return str;
    }
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        dfs(root);
        return res;
    }
};