题目描述

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

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

样例

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4

下面是两个重复的子树：

      2
     /
    4

和

    4

因此，你需要以列表的形式返回上述重复子树的根结点。

算法1

(哈希表) $O(n^2)$

首先子树的定义为以树中某个节点为根并且包含该节点所有子节点的树，所以如果一个树有n个节点则它有n棵子树。

那么我们就可以序列化这n棵子树并且用哈希表来存储，当我们第一次遇见重复的子树时将当前根节点加入答案。

对于序列化我们可以将树的前序遍历变成一个字符串，注意这里要包含空节点不然不同的树可能序列化出相同的字符串，而且我们不能用树的中序遍历来序列化，原因是即使包含空节点不同的树依然有可能序列化出相同的字符串。比如下面这个例子：

   0         0
  /     和    \
 0             0 

用中序遍历的话结果都为[null, 0, null, 0, null]。而用前序遍历则会不一样。

时间复杂度

因为这n棵子树的序列化表示共需要$O(n^2)$个字符，所以时间复杂度为$O(n^2)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        vector<TreeNode*> res;
        unordered_map<string, int> hash;
        dfs(root, res, hash);
        return res;
    }

    string dfs(TreeNode* root, vector<TreeNode*>& res, unordered_map<string, int>& hash)
    {
        if (!root) return "#";
        string s = to_string(root->val) + "#";
        s += dfs(root->left, res, hash);
        s += dfs(root->right, res, hash);
        if (hash[s] == 1) res.push_back(root);
        hash[s] ++ ;
        return s;
    }
};

算法2

(哈希表) $O(n)$

本题还可以继续优化，可以发现时间复杂度主要取决于所有子树序列化后的字符串的长度，所以我们可以再做一层哈希，将每棵不同的子树（字符串）映射为一个数（即Id），这样对于每棵子树我们可以表示成(root->val, id of left subtree, id of right subtree)的三元组的形式，这个三元组每个元素都是一个数，是 $\log_{10}n$ 级别的，比如我们可以用 $6$ 位数表示 $10^6$ 个不同的子树，这样总长度就是 $O(n)$ 级别的了（近似）。另外由于我们需要记录重复的子树，所以我们需要另外一个哈希表来存储每棵子树出现的次数（也可以只用一个哈希表，用一个pair来分别存储id和次数）。

如果觉得上述过程有些抽象的话可以将样例中每棵子树序列化后的结果打印出来，这样就很容易看出来每棵子树的长度被大大缩短了。

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4

一重哈希：
4,null,null
2,4,null,null,null
4,null,null
2,4,null,null,null
4,null,null
3,2,4,null,null,null,4,null,null
1,2,4,null,null,null,3,2,4,null,null,null,4,null,null


两重哈希：
4,0,0
2,1,0
4,0,0
2,1,0
4,0,0
3,2,1
1,2,3

时间复杂度

现在这n棵子树的序列化表示共需要$O(n)$个字符，所以时间复杂度为$O(n)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int id;
    unordered_map<string, int> hash;
    unordered_map<int, int> mp;
    vector<TreeNode*> res;
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        id = 0; // 空节点编号为0
        dfs(root);
        return res;
    }

    int dfs(TreeNode* root) 
    {
        if (!root) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);

        string cur = to_string(root->val) + "," + to_string(left) + "," + to_string(right);
        if (!hash.count(cur)) hash[cur] = ++ id;
        int t = hash[cur];
        if (++ mp[t] == 2) res.push_back(root);
        return t;
    }
};