给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
两棵树重复是指它们具有相同的结构以及相同的结点值。
示例 1：
1 / \ 2 3 / / \ 4 2 4 / 4下面是两个重复的子树：
2 / 4和
4因此，你需要以列表的形式返回上述重复子树的根结点。
我的思路：
把每个子树化为字符串存入map里，如果发现有重复字符串，也就是有重复子树，就把这个重复子树加入结果集中。
代码：
class Solution { public: vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) { vector<TreeNode*> ans;//结果集 if (root == NULL) { return ans; } map<string, int> mp;//map字符串集 dfs(root, ans, mp);//递归，深度优先 return ans; } string dfs(TreeNode* root, vector<TreeNode*> &ans, map<string, int> &mp) { if (root == NULL) { return "#";//空节点字符串视为“#” } string temp = to_string(root->val) + dfs(root->left, ans, mp) + dfs(root->right, ans, mp);//找到子树左右节点的字符串 if (mp[temp] == 1)//判断之前有没有出现重复子串,如果等于2或以上就说明之前已经计算过了 { ans.push_back(root);//如果有重复子串，就把节点加入结果集中 } mp[temp]++;//该字符串出现次数加一 return temp; } };
