继续每日分享一道算法题，监督自己学习，不落下算法，有需要一起打卡的uu，可以一起加油呀！

好了，现在开始看题了哈：

给定一棵二叉树 root，返回所有重复的子树。

对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

如果两棵树具有相同的结构和相同的结点值，则它们是重复的。

思路

首先我们看到是找相同的子树，我们是不是得先理解什么是两棵相同的子树。相同的子树，顾名思义，是不是就是两个子树的结点对应的节点都一样，比如看示例1，我们是不是很容易就可以发现上述图的子树2-4 是重复出现了两次，所以我们肯定是先想到，我只要进行暴力就好了呀，每一个结点都进行暴力查找。

这肯定是不行的嘛，所以我们就想办法把每个子树的结点都记录下来，这样通过次数就可以知道该子树是否有重新出现了嘛，所以嘛，我们肯定先想到哈希表来记录出现的次数。

那hash的key呢，我们怎么确定呢。我们可以通过递归遍历的序列来充当key值，这样就可以了哈。

看到这里了，看代码吗？还是先去AC？

查找重复的子树

代码

/**

 *@author DY

 *@date 2022/4/20

 */

class Solution {

    /*

     *  cnt记录序列化出现的次数

     *  ans保存重复出现的树节点

     */

    Map<String,Integer> cnt ;

    List<TreeNode> ans ;

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {

        cnt = new HashMap<>();

        ans = new LinkedList<>();

        find(root);

        return ans;

    }

    public String find(TreeNode root){

        //出口，叶子节点

        if(root == null){

            return "#";

        }

        //模板，先递归左子树，再递归右子树

        String left = find(root.left);

        String right = find(root.right);

        // 这里记录的是子树的序列，当两个序列一样的时候，说明两个子树一样

        String Ans = root.val+"."+left+"."+right;

        // 获取当前这个子树的出现次数

        int num = cnt.getOrDefault(Ans,0);

        // 当这个子树已经出现后，我们直接将这个节点加入到重复出现的列表中

        if(num ==1){

            ans.add(root);

        }

        //更新当前子树的次数

        cnt.put(Ans,num+1);

        return Ans;

    }

}

总结

这里就分享了一种做法，通过哈希记录+搜索，继续督促自己学习，加油！

LeetCode刷题之652寻找重复的子树的相关教程结束。