652. Find Duplicate Subtrees

Version #2
基本思路还是差不多，比Version#1好一些
map.getOrDefault(curr, 0) 这个method 用着很不错哎 Mark一下

 53.39 %
HashMap key-> String, value -> count of Nodes with same string
If and only if count == 2, we add current node into result list
if (count == 1) duplicate hasn't been found yet
if (count > 2) this result has already added into the result list

class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> result = new ArrayList<>();
        if (root == null) return result;
        Map<String, Integer> map = new HashMap<>();
        dfsHelper(root, map, result);
        return result;
    }
    private String dfsHelper(TreeNode root, Map<String, Integer> map, List<TreeNode> result) {
        if (root == null) return "#";
        String curr = root.val + "/" + dfsHelper(root.left, map, result) + "/" + dfsHelper(root.right, map, result);
        if (map.getOrDefault(curr, 0) == 1) result.add(root);
        map.put(curr, map.getOrDefault(curr, 0) + 1);
        return curr;
    }
}


Version #1
HashMap 的key是String，value是TreeNode
因为一组相同的subTree只记录其中一个，所以用一个HashSet记录看到过的subTree Root
看了Version#2 的答案感觉不如Version#2写的好
29.41 %
class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        // key-serialized string of subtree, value-the node
        if (root == null) return new ArrayList<TreeNode>();
        Map<String, TreeNode> map = new HashMap<>();
        Set<TreeNode> set = new HashSet<>();
        // TODO
        dfsHelper(root, map, set);
        return new ArrayList<TreeNode>(set);
    }
    private String dfsHelper(TreeNode root, Map<String, TreeNode> map, Set<TreeNode> set) {
        if (root == null) {
            return "#";
        }
        String curr = root.val + "/" + dfsHelper(root.left, map, set) + "/" + dfsHelper(root.right, map, set);
        if (map.containsKey(curr)) {
            set.add(map.get(curr));
        } else {
            map.put(curr, root);
        }
        return curr;
    }
}