📃 题目描述

题目链接：

• 652. 寻找重复的子树 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题华为机考（2022.3.30 号）考过，原题

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

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

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

示例 1：

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

🔔 解题思路

当出现需要判断是否重复时，需要想到使用 Map，key为二叉树的遍历结果（使用序列化的方式，将数据打平），value为对应该遍历结果出现的频率。

使用后序遍历，先获取左子树，然后再获取右子树，将本子树序列化，然后存储到 map中，如果出现频率出现 2 次，就表示出现重复子树

class Solution {

    // key: 子树结构 value: 该结构出现的次数
    private Map<String, Integer> map = new HashMap<>();
    // 存储重复子树的根节点
    private List<TreeNode> res = new ArrayList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        if (root == null) {
            return res;
        }
        serialize(root);
        // 返回的是重复子树的根结点（多个）
        return res;
    }
    
    // 序列化（后序遍历和先序遍历都行，唯独中序遍历不行）以当前节点为根节点的二叉树
    private String serialize(TreeNode root) {
        if (root == null) {
            return "null";
        }
       
        
        // 后序遍历
        String str1 = serialize(root.left);
        String str2 = serialize(root.right);
        String str = str1 + "," + str2 + "," + root.val;

        // 更新 map
        map.put(str, map.getOrDefault(str, 0) + 1);

        // 重复子树，加入 res
        if (map.get(str) == 2) {
            res.add(root);
        }

        return str;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：