# 0652. Find Duplicate Subtrees
###### tags: `Leetcode` `Medium` `Tree`
Link: https://leetcode.com/problems/find-duplicate-subtrees/
## 思路
用字符串存所有可能的subtree 并当作map的key map的value里面放subtree是key的所有node
## Code

class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        Map<String, List<TreeNode>> map = new HashMap<>();
        serialize(root, map);
        List<TreeNode> ans = new ArrayList<>();
        for(String key:map.keySet()){
            if(map.get(key).size()>1){
                ans.add(map.get(key).get(0));
            }
        }
        return ans;
    }
    private String serialize(TreeNode root, Map<String, List<TreeNode>> map){
        if(root==null) return "";
        String s = "("+serialize(root.left, map)+root.val+serialize(root.right, map)+")";
        if(!map.containsKey(s)) map.put(s, new ArrayList<TreeNode>());
        map.get(s).add(root);
        return s;
    }
}