652. 寻找重复的子树

一、题目描述：

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

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

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

示例 1：

输入：root = [1,2,3,4,null,2,4,null,null,4]
输出：[[2,4],[4]]
示例 2：

输入：root = [2,1,1]
输出：[[1]]
示例 3：

输入：root = [2,2,2,3,null,3,null]
输出：[[2,3],[3]]

提示：

树中的结点数在[1,10^4]范围内。
-200 <= Node.val <= 200

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

二、思路分析：

首先解决如何寻找重复的问题，要找重复的子树，如果重复了就保存一个树的根节点。这已经提示我们，遍历整棵树的所有节点，遍历的时候我们想办法得到以这个结点为根的子树的情况是什么样子的，显然用序列化二叉树，如何记录重复？这里我想到用哈希如果对应子树的序列出现次数超过1次那么就重复了，需要在结果中加入该子树的根结点。
再就是如何遍历树？我们知道树分三种遍历方式：前序，中序和后序，这三种都是深度优先搜索DFS。当然还有层次遍历，广度优先搜索BFS是可行的，

三、AC 代码：

class Solution {
    Map<String,Integer> tree = new HashMap();
    List<TreeNode> answer = new LinkedList<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        traverse(root);
        return answer;
    }
    private String traverse(TreeNode root) {
        if(root == null) {
            return "#";
        }
        //得到序列化后的左子树
        String leftTree = traverse(root.left);
        //得到序列化后的右子树
        String rightTree = traverse(root.right);
        String treeSub = root.val + "," + leftTree + "," + rightTree;
        int count = tree.getOrDefault(treeSub,0);
        //如果存在该子树
        if(count == 1) {
            answer.add(root);
        }
        //子树数量递增
        tree.put(treeSub,count+1);
        return treeSub;
    }
}