题目

标题和出处

标题：寻找重复的子树

出处：652. 寻找重复的子树

难度

7 级

题目描述

要求

给定二叉树的根结点 $\text{root}$，返回所有重复的子树。

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

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

示例

示例 1：

输入：$\text{root = [1,2,3,4,null,2,4,null,null,4]}$
输出：$\text{[[2,4],[4]]}$

示例 2：

输入：$\text{root = [2,1,1]}$
输出：$\text{[[1]]}$

示例 3：

输入：$\text{root = [2,2,2,3,null,3,null]}$
输出：$\text{[[2,3],[3]]}$

数据范围

• 树中结点数目在范围 $\text{[1, 5000]}$ 内
• $\text{-200}\le \text{Node.val}\le \text{200}$

解法

思路和算法

两个子树是重复的子树等价于两个子树的结构和结点值都相同。为了表示每个子树的结构和结点值，需要将子树序列化，然后判断每个序列化出现的次数，序列化出现次数超过 $1$ 次的子树为重复的子树。序列化需要满足任意两个不重复的子树的序列化结果不同。

一种序列化的方式是存储子树的前序遍历的结果，包括空结点，即如果一个非空结点的某个子结点为空，则空的子结点也需要包含在序列化的结果中。序列化的结果中，非空结点使用结点值表示，空结点使用字符 $\text{‘\#’}$ 表示，每个结点之间使用逗号分隔。

例如，示例 1 的整个二叉树的序列化结果是 $\text{“1,2,4,\#,\#,\#,3,2,4,\#,\#,\#,4,\#,\#"}$。

由于上述序列化的结果为前序遍历的结果，因此可以使用深度优先搜索实现序列化。序列化的过程是递归的过程，递归的终止条件是当前结点为空，此时返回 $\text{“\#"}$。对于其余情况，首先将当前子树的根结点值加入当前子树的序列化结果，然后依次对当前子树的左子树和右子树序列化，并将结果拼接到当前子树的序列化结果中，根结点、左子树和右子树之间都需要加逗号分隔。

为了得到重复的子树，需要使用哈希表存储每个序列化的结果的出现次数，在序列化每个子树的过程中维护每个序列化的结果的出现次数。当得到一个子树的序列化的结果之后，将当前序列化的结果在哈希表中的次数加 $1$。如果当前序列化的结果在哈希表中的次数变成 $2$，则将当前子树加到结果中。上述做法可以确保只有重复的子树会加到结果中，且同一类的重复子树只会在结果中出现一次。

证明

上述序列化的结果可以确保任意两个不重复的子树的序列化结果不同，证明如下。

对于序列化结果中的两个相邻的值 $x$ 和 $y$（都可能是非空结点或空结点），结点 $x$ 和结点 $y$ 的关系可能是以下三种情况之一：

• 如果结点 $x$ 不为空，则结点 $y$ 是结点 $x$ 的左子结点；

• 如果结点 $x$ 为空，且结点 $x$ 是其父结点的左子结点，则结点 $y$ 是结点 $x$ 的父结点的右子结点；

• 如果结点 $x$ 为空，且结点 $x$ 是其父结点的右子结点，则结点 $y$ 是结点 $x$ 的祖父结点的右子结点。

上述三种情况都可以在已知结点 $x$ 的情况下唯一地确定结点 $y$ 的位置，因此同一个序列化的结果对应的树结构和结点值是唯一的，不可能有两个不重复的子树得到相同的序列化结果。

代码

class Solution {Map<String, Integer> encodeCountMap = new HashMap<String, Integer>();List<TreeNode> duplicateSubtrees = new ArrayList<TreeNode>();public List<TreeNode> findDuplicateSubtrees(TreeNode root) {encode(root);return duplicateSubtrees;}public String encode(TreeNode node) {if (node == null) {return "#";}StringBuffer sb = new StringBuffer();sb.append(node.val);sb.append(',');sb.append(encode(node.left));sb.append(',');sb.append(encode(node.right));String encoded = sb.toString();encodeCountMap.put(encoded, encodeCountMap.getOrDefault(encoded, 0) + 1);if (encodeCountMap.get(encoded) == 2) {duplicateSubtrees.add(node);}return encoded;}
}

复杂度分析

• 时间复杂度：$O(n^2)$，其中 $n$ 是二叉树的结点数。每个结点都被访问一次，对于每个子树序列化需要 $O(n)$ 的时间，因此总时间复杂度是 $O(n^2)$。

• 空间复杂度：$O(n^2)$，其中 $n$ 是二叉树的结点数。使用哈希表存储每个子树的序列化，需要 $O(n^2)$ 的空间。