给定一棵二叉树 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]]
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-duplicate-subtrees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方法一：暴力
遍历整个树，每个结点都添加到list集合中，最后再来比较每个是否有重复的
方法二：三元组优化
三元组优化了空间时间，利用编号代替了每个结点的子节点，节省了大量的时间和空间，相等的结点编号相同。
- 思路：
- 深搜搜到叶子结点，然后从叶子节点网上回溯，就能知道每个结点的子节点情况（就能判断该结点是否重复），空结点编号为0
- 用一个三元数组唯一标识一个结点，[当前结点value,左结点编号，右结点编号]
- 利用map判断当前三元组是否出现过，
- 通过结构体将树和当前树根节点的编号值存储起来
- map<三元组，结构体>
java代码实现（详细注释）
class Solution {
Map<String, Pair<TreeNode,Integer>> map = new HashMap<>();
Set<TreeNode> set = new HashSet<>(); //用来存储重复的子树
int index = 0; //记录每个树的编号
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
DFS(root);
List<TreeNode> list = new ArrayList<>(set);
return list;
}
private int DFS(TreeNode root) {
//0.递归先写出口
if (root == null) {
return 0;
}
//1.得到递归遍历得到三元组，并转化为字符串
int[] Three = {root.val, DFS(root.left), DFS(root.right)};
String Key = Arrays.toString(Three); //
//2.先判断当前结点是否存在
if (map.containsKey(Key)) {//存在
//3.说明当前结点重复了,将当前结点添加到set集合中，并且当前结点已经存在，那么就不需要再创建新的编号
Pair<TreeNode, Integer> pair = map.get(Key);
set.add(pair.getKey());
return pair.getValue();
} else {//不在哈希表中
//4.将当前结点添加到哈希表中，并且创建新的编号
map.put(Key,new Pair<>(root,++index));
return index;
}
}
}
