[LeetCode] 652. Find Duplicate Subtrees 寻找重复树
LeetCode 重复 Find 寻找 Duplicate
2023-09-11 14:21:37 时间
Given the root
of a binary tree, return all duplicate subtrees.
For each kind of duplicate subtrees, you only need to return the root node of any one of them.
Two trees are duplicate if they have the same structure with the same node values.
Example 1:
Input: root = [1,2,3,4,null,2,4,null,null,4] Output: [[2,4],[4]]
Example 2:
Input: root = [2,1,1] Output: [[1]]
Example 3:
Input: root = [2,2,2,3,null,3,null] Output: [[2,3],[3]]
Constraints:
- The number of the nodes in the tree will be in the range
[1, 10^4]
-200 <= Node.val <= 200
这道题让我们寻找重复树,博主开始的思路是遍历每个结点,将结点值相同的结点放到一起,如果再遇到相同的结点值,则调用一个判断是否是相同树的子函数,但是这样会有大量的重复运算,会TLE。后来去网上看大神们的解法,发现果然是很叼啊,用到了后序遍历,还有数组序列化,并且建立序列化跟其出现次数的映射,这样如果得到某个结点的序列化字符串,而该字符串正好出现的次数为1,说明之前已经有一个重复树了,将当前结点存入结果res,这样保证了多个重复树只会存入一个结点,参见代码如下:
class Solution { public: vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) { vector<TreeNode*> res; unordered_map<string, int> m; helper(root, m, res); return res; } string helper(TreeNode* node, unordered_map<string, int>& m, vector<TreeNode*>& res) { if (!node) return "#"; string str = to_string(node->val) + "," + helper(node->left, m, res) + "," + helper(node->right, m, res); if (m[str] == 1) res.push_back(node); ++m[str]; return str; } };
同步地址:
https://github.com/grandyang/leetcode/issues/652
参考资料:
https://leetcode.com/problems/find-duplicate-subtrees/
相关文章
- Leetcode 之Longest Valid Parentheses(39)
- Java实现 LeetCode 712 两个字符串的最小ASCII删除和(最长公共子串&&ASCII值最小)...
- Java实现 LeetCode 565 数组嵌套(没有重复值的数组)
- Java实现 LeetCode 395 至少有K个重复字符的最长子串
- Java实现 LeetCode 287 寻找重复数
- Java实现 LeetCode 212 单词搜索 II(二)
- Java实现 LeetCode 83 删除排序链表中的重复元素
- Java实现 LeetCode 61 旋转链表
- Java实现 LeetCode 56 合并区间
- Java实现 LeetCode 12 整数转罗马数字
- 【LeetCode Python实现】17. 电话号码的字母组合(中等)
- Leetcode 1209. 删除字符串中的所有相邻重复项 II(牛逼,终于过了)
- Leetcode 1598. 文件夹操作日志搜集器
- Leetcode 1296. 划分数组为连续数字的集合(已解决)
- leetcode 26 Remove Duplicates from Sorted Array
- 【leetcode】leetcode3 无重复字符的最长子串