• Time:O(n)
• Space:O(n)

## C++

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)
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;
}
};

## JAVA

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)
return encoded;
}
}

## Python

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