给你一棵二叉树的根节点 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;
- }
- };