2022-09-05力扣每日一题（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]]

来源：力扣（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;
            }
        }

    }