LeetCode Solutions
652. Find Duplicate Subtrees
Time: $O(n)$ Space: $O(n)$
class Solution {
public:
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
vector<TreeNode*> ans;
unordered_map<string, int> count;
encode(root, count, ans);
return ans;
}
private:
string encode(TreeNode* root, unordered_map<string, int>& count,
vector<TreeNode*>& ans) {
if (root == nullptr)
return "";
const string encoded = to_string(root->val) + "#" +
encode(root->left, count, ans) + "#" +
encode(root->right, count, ans);
if (++count[encoded] == 2)
ans.push_back(root);
return encoded;
}
};
class Solution {
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
List<TreeNode> ans = new ArrayList<>();
Map<String, Integer> count = new HashMap<>();
encode(root, count, ans);
return ans;
}
private String encode(TreeNode root, Map<String, Integer> count, List<TreeNode> ans) {
if (root == null)
return "";
final String encoded =
root.val + "#" + encode(root.left, count, ans) + "#" + encode(root.right, count, ans);
count.merge(encoded, 1, Integer::sum);
if (count.get(encoded) == 2)
ans.add(root);
return encoded;
}
}
class Solution:
def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
ans = []
count = Counter()
def encode(root: Optional[TreeNode]) -> str:
if not root:
return ''
encoded = str(root.val) + '#' + \
encode(root.left) + '#' + \
encode(root.right)
count[encoded] += 1
if count[encoded] == 2:
ans.append(root)
return encoded
encode(root)
return ans