# 652. Find Duplicate Subtrees

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any oneof them.

Two trees are duplicate if they have the same structure with same node values.

Example 1:

1
/ \
2   3
/   / \
4   2   4
/
4

The following are two duplicate subtrees:

2
/
4

and

4

Therefore, you need to return above trees’ root in the form of a list.

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://discuss.leetcode.com/topic/97584/java-concise-postorder-traversal-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation