LeetCode刷题系列 -- 652. 寻找重复的子树

给你一棵二叉树的根节点 root ，返回所有 重复的子树 。

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

如果两棵树具有 相同的结构 和 相同的结点值 ，则认为二者是 重复 的。

示例 1：

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

输入：root = [2,1,1]
输出：[[1]]
示例 3：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-duplicate-subtrees
 

思路：

定义一个 map，其 key 为当前节点 root 前序遍历后的字符串，value 为 以该字符串为前序遍历的节点的个数；

定义 vector ，当发现 某个字符串出现的次数为 2 时，该字符串对应的节点即为题目所求的一个结果，并存到 vector 中

c++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<string, int> ump;
    vector<TreeNode*> ans;
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        dfs(root);
        return ans;
    }
 
    string dfs(TreeNode* root){
        if(root == nullptr) {
            return "";
        }
 
        string key = to_string(root->val) +"(" + dfs(root->left) +")(" + dfs(root->right)+")";
 
        ump[key] += 1;
 
        if(ump[key] == 2) {
            ans.push_back(root);
        }
 
        return key;
    }
};