LeetCode 652. 寻找重复的子树

Categories:

题目描述
思路分析
1. 解法一：序列化 + 哈希计数（推荐）
相似题目

题目描述

✅ 652. 寻找重复的子树

思路分析

解法一：序列化 + 哈希计数（推荐）

核心思路：

对每棵子树进行后序序列化：val,left,right。

使用哈希表统计序列化字符串出现次数。

当某序列化第一次重复时加入结果。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数量。

空间复杂度：O(n)，存储序列化字符串。

class Solution {
    private final Map<String, Integer> count = new HashMap<>();
    private final List<TreeNode> res = new ArrayList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        dfs(root);
        return res;
    }

    private String dfs(TreeNode node) {
        if (node == null) {
            return "#";
        }

        String left = dfs(node.left);
        String right = dfs(node.right);
        String serial = node.val + "," + left + "," + right;

        int c = count.getOrDefault(serial, 0);
        if (c == 1) {
            res.add(node);
        }
        count.put(serial, c + 1);

        return serial;
    }
}

func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
	count := make(map[string]int)
	res := make([]*TreeNode, 0)

	var dfs func(*TreeNode) string
	dfs = func(node *TreeNode) string {
		if node == nil {
			return "#"
		}
		left := dfs(node.Left)
		right := dfs(node.Right)
		serial := fmt.Sprintf("%d,%s,%s", node.Val, left, right)

		count[serial]++
		if count[serial] == 2 {
			res = append(res, node)
		}
		return serial
	}

	dfs(root)
	return res
}

相似题目

题目	难度	考察点
297. 二叉树的序列化与反序列化	困难	序列化
652. 寻找重复的子树	中等	哈希
105. 从前序与中序遍历序列构造二叉树	中等	递归
889. 根据前序和后序遍历构造二叉树	中等	递归
572. 另一棵树的子树	简单	序列化

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/76202176