力扣(LeetCode)652

题目地址：

https://leetcode-cn.com/probl...

题目描述：

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

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

示例 1：

1
   / \
  2   3
 /   / \
4   2   4
   /
  4

下面是两个重复的子树：

2
 /
4

和

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

解答：

如何判断两棵树是重复的？只要两棵树的先序(各种序都可以)遍历结果是一样的，那么这两棵树就是重复的？

不一定！！！

2
 /
4

和

2

\

4

它们的先序遍历结果就是相同的，但是并不重复。为什么？因为遍历的时候忽略掉了空树的位置。

但是如果先序访问这个树的时候保留空树(也就是访问空树)，那么此时就成立了！先序遍历树并

且对它进行序列化，空树的序列化结果为" "，而对于任意节点root它的序列化结果为"root.val 左子树序列化 右子树序列化"。这里再用hashmap存储，键：序列化结果，值：树节点组成的链表。最后序列化完，遍历这个hashmap，找到hashmap中，值(链表)长度大于1的位置，把这个位置链表的第一个节点放入答案集，按照这个思路就能理解下面的代码：

java ac代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    HashMap<String,List<TreeNode>> map = new HashMap(1000);

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        serialize(root);
        List<TreeNode> ans = new ArrayList(1000);
        for(Map.Entry<String,List<TreeNode>> entry:map.entrySet())
            if(entry.getValue().size()>1)
            ans.add(entry.getValue().get(0) );
        return ans;
    }
    
    public String serialize(TreeNode root)
    {
        if(root == null)return " ";
        String temp = root.val+" "+serialize(root.left)+" "+serialize(root.right);
        if(map.get(temp) == null){
            List<TreeNode> list = new LinkedList();
            list.add(root);
            map.put(temp,list);
        }
        else map.get(temp).add(root);
        return temp;
    }
    
}