题目描述

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

两棵树重复是指它们具有相同的结构以及相同的结点值。

样例

算法1

(一遍哈希) $O(n^2)$

利用前序遍历将树序列化，dfs枚举所有的子树序列str，并将str存在hash表中，如果出现两次以上，将本子树的根节点加入结果中。

参考https://www.acwing.com/activity/content/code/content/99569/

C++ 代码

class Solution {
public:
    unordered_map<string, int> hash;
    vector<TreeNode*> res;
    // itn cnt = 0;

    string dfs(TreeNode* root){
        if(!root) return "#";
        string left = dfs(root->left);
        string right = dfs(root->right);
        string str = to_string(root->val) + ',' + left + ',' + right;
        ++hash[str];
        if(hash[str] == 2) res.push_back(root);
        return str;

    }
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        if(!root) return res;
        dfs(root);
        return res;
    }
};

算法2

(两次hash) $O(n)$

在方法1的基础上，将前序遍历得到的子树序列str再进行一次hash映射。因为树n个节点得到n个字符串str，每个字符串的hash操作时间复杂度是o(n),操作n个字符串，时间o(n^n)。所以再次将str-> 映射到一个新的hash表，

C++ 代码

class Solution {
public:
    unordered_map<string, int> hash;
    unordered_map<int, int> count;
    int cnt = 0;
    vector<TreeNode*> res;
    // itn cnt = 0;

    string dfs(TreeNode* root){
        if(!root) return "#";
        string left = dfs(root->left);
        string right = dfs(root->right);
        string str = to_string(root->val) + ',' + left + ',' + right;
        if(hash.find(str) == hash.end()) {
            cnt++;
            hash[str] = cnt;
        }
        int t = hash[str];
        ++count[t];
        if(count[t] == 2) res.push_back(root);
        return str;

    }
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        if(!root) return res;
        dfs(root);
        return res;
    }
};