Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of anyoneof 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.

Solution: post order traverse树，把每棵子树序列化为string，放在hashmap。当该string在之前出现过一次，把cur node加入list。string中逗号的存在确保了该traversal对应相同的子树。eg:

    1     1
   /       \
  2         2
 /           \
3             3

分别是："1, 2, 3, , , ," 和 "1, , 2, , 3, ,"

    Map<String, Integer> hashmap;
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> ans = new ArrayList<>();
        hashmap = new HashMap<>();
        postorder(root, ans);
        return ans;
    }

    private String postorder(TreeNode root, List<TreeNode> ans) {
        if (root == null) {
            return "";
        }
        //产生的string是preorder
        String serial = root.val + "," + postorder(root.left, ans) + "," + postorder(root.right, ans);
        if (hashmap.getOrDefault(serial, 0) == 1) {
            ans.add(root);
        }
        hashmap.put(serial, hashmap.getOrDefault(serial, 0) + 1);
        return serial;
    }