LeetCode652-寻找重复的子树

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/find-duplicate-subtrees/

中文链接：https://leetcode-cn.com/problems/find-duplicate-subtrees/

题目详述

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

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

示例 1：

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

下面是两个重复的子树：

  2
 /
4

和

4

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

题目详解

  • 两棵树重复是指它们具有相同的结构以及相同的结点值。为了方便判断，需要对数进行序列化。
  • 如果发现序列化得到的字符串出现次数超过 1 次，说明对应的两颗树重复。
  • LeetCode297-二叉树的序列化与反序列化 提供了二叉树的先序遍历的序列化方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LeetCode_00652 {

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> res = new ArrayList<>();
        dfs(root, new HashMap<>(), res);
        return res;
    }

    private String dfs(TreeNode root, Map<String, Integer> map, List<TreeNode> res) {
        if (root == null) {
            return "";
        }
        String s = root.val + "_" + dfs(root.left, map, res) + "_" + dfs(root.right, map, res);
        map.put(s, map.getOrDefault(s, 0) + 1);
        if (map.get(s) == 2) {
            res.add(root);
        }
        return s;
    }
}