leetcode 652

class Solution {

/*    //记录所有子树
    HashSet<String> memo = new HashSet<>();*/

    //记录所有子树及其出现次数
    HashMap<String, Integer> memo = new HashMap<>();
    //记录重复的子树根节点
    LinkedList<TreeNode> res = new LinkedList<>();

    /* 主函数 */
    List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        traverse(root);
        return res;
    }


    //后序遍历
    String traverse(TreeNode root){
        if(root == null){
            return "#";
        }
        String left = traverse(root.left);
        String right = traverse(root.right);

        String subTree = left + "," + right + "," + root.val;

        //由于需要memo记录所有的子树，所以采用后序遍历的算法
        //getOrDefault接口 - map中有这个值，就用这个值，没有就用默认值
        int freq = memo.getOrDefault(subTree, 0);
        //只加入一次结果集
        if(freq == 1){
            res.add(root);
        }
        memo.put(subTree, freq + 1);
/*        if(memo.contains(subTree)){
            res.add(root);
        }else {
            memo.add(subTree);
        }*/
        return subTree;
    }
}