共计 1193 个字符，预计需要花费 3 分钟才能阅读完成。
题目地址：https://leetcode-cn.com/probl… 题目描述：给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
两棵树重复是指它们具有相同的结构以及相同的结点值。
示例 1：
1
/ \
2 3
/ / \
4 2 4
/
4
下面是两个重复的子树：
2
/
4
和
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;
}
}
