652-寻找重复的子树

LeetCode 652. 寻找重复的子树

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

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

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

示例 1：

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

method

如果两棵子树是相同的，那它们序列化的结果也是一样的，所以用哈希表存储每棵子树的序列化结果，看有没有重复的

unordered_map<string, int> hash;
vector<TreeNode*> res;
string serialize(TreeNode* root) {
    if (!root) return "#";
    string cur = to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);
    hash[cur]++;
    if (hash[cur] == 2) res.push_back(root);    // 存一次就行
    return cur;
}
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
    serialize(root);
    return res;
}