本文共 877 字，大约阅读时间需要 2 分钟。

力扣 652. 寻找重复的子树 题解 java实现

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

两棵树重复是指它们具有相同的结构以及相同的结点值。

示例 1：

因此，你需要以列表的形式返回上述重复子树的根结点。

思路

找到以当前节点的树结构，然后存入HashMap里面，顺便记录出现次数，当出现次数为1次的时候加入结果，找到当前根节点的树结构用后序遍历

class Solution {       List
   
     res = new LinkedList<>();    //记录次数    HashMap
    
      map = new HashMap<>();    public List
     
       findDuplicateSubtrees(TreeNode root) {           traverse(root);        return res;    }    public String traverse(TreeNode root){           //终止条件       if(root == null) return "#";       String left = traverse(root.left);       String right = traverse(root.right);       //后序遍历可以得到根节点的树结构       String sub = left + "," + right + "," + root.val;       //查找出现次数，没有出现赋值为0       int i = map.getOrDefault(sub, 0);       //只有出现次数为1的时候才会放入结果       if(i == 1) res.add(root);       //次数加一       map.put(sub, i+1);       return sub;    }}