652. Find Duplicate Subtrees

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with same node values.

Example 1:

        1
       /       2   3
     /   /     4   2   4
       /
      4

The following are two duplicate subtrees:

      2
     /
    4

and

    4

Therefore, you need to return above trees‘ root in the form of a list.

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

用一个hashmap记录每个node对应的hash string的频率（hash就是root val string加上它的左右子，很玄学，记得要加个逗号）。

然后这个实际上是一个postorder添加到map中，但看起来hash的时候是preorder，如果这个hash出现了一次就要把这个root添加到res中

652. Find Duplicate Subtrees

原文：https://www.cnblogs.com/wentiliangkaihua/p/13456418.html