1、前言

2、思路

这道题的意思一开始确实难以理解，什么叫重复子树？

重复子树说的是两个子树具有相同的结构，而且值相同。也就是说，一个为左子树，那么另一个一定为左子树，且对应节点上的值是一模一样的。然后根据这种定义参考题目的示例。

这道题考一个后续遍历，我理解二叉树的后续遍历是一个自底向上的过程（即先遍历到最深入的一个节点再依次向上返回），与之相反的先序遍历则是一个自顶向下的过程。

那么我们就根据后续遍历，一直到底部，然后将此节点变成字符串存储起来，只要遇到相同的就把节点记录下来。因为相同的节点可以有多个，所以只记录重复次数为1的。

3、代码

class Solution {
    Map<String, Integer> map = new HashMap<>();
    List<TreeNode> res = new ArrayList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        dfs(root);
        return res;
    }

    private String dfs(TreeNode root) {
        if(root == null) {
            return "#";
        }
        
        String left = dfs(root.left);
        String right = dfs(root.right);
        String subTree = left + "," + right + "," + root.val;
        int times = map.getOrDefault(subTree, 0);
        if(times == 1){
            res.add(root);
        }
        map.put(subTree, map.getOrDefault(subTree, 0) + 1);
        return subTree;
    }
}