力扣 652. 寻找重复的子树

给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
两棵树重复是指它们具有相同的结构以及相同的结点值。

    1
   / 
  2   3
 /   / 
4   2   4
   /
  4

下面是两个重复的子树：

  2
 /
4

和

4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-duplicate-subtrees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

使用后序遍历，将二叉树递归序列化。
每次序列化的结果s和出现的次数存在字典里。出现了两次的将子树的根节点存在列表里，最后返回res。

方法1：python

class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        def find(root):
            if root is None:
                return "#"
            left=find(root.left)
            right=find(root.right)

            s=left+","+right+","+str(root.val)
            freq=memo.get(s,0)
            if freq==1: res.append(root)
            memo[s]=freq+1
            return s
        
        res=list()
        memo=dict()
        find(root)
        return res

方法2：java

class Solution {
    // 存储每棵子树及出现的次数
    HashMap trees = new HashMap<>();
    // 存储重复子树
    List res = new ArrayList<>();

    public List findDuplicateSubtrees(TreeNode root) {
        getDuplicateTrees(root);

        return res;
    }

    // 遍历每棵子树存入hashmap
    public String getDuplicateTrees(TreeNode root) {
        if (root == null) {
            return "#";
        }
        // 递归左右子树
        String left = getDuplicateTrees(root.left);
        String right = getDuplicateTrees(root.right);
        // 构造子树标志
        String tree = left + "," + right + "," + root.val;
        // 存入hashmap
        trees.put(tree, trees.getOrDefault(tree, 0) + 1);
        // 如果重复
        if (trees.get(tree) == 2) {
            res.add(root);
        }

        return tree;
    }
}