LeetCode 652. 寻找重复的子树
目录
题目描述
题意分析
输入一棵二叉树，要求把「长得完全一样」的子树找出来。这里的「一样」指结构一样且对应位置的值也一样，不是只看节点集合或节点个数。
输出的约定很关键：同一种重复子树，无论出现两次还是五次，答案里只放一个根节点，且放哪一个都算对。这句话直接决定了统计逻辑不能写成「只要重复就加」。
约束信号：节点数上限只有 $10^4$，值域是 $[-200, 200]$。规模小说明允许把每棵子树整体压成一个可比较的表示；值域含负数提醒我们，拼接表示时不能让
-1和1之间产生歧义。边界情况：整棵树只有一个节点时不存在重复；两个子树一个是「左孩子为空」、另一个是「右孩子为空」但值相同，它们不算重复，必须能区分开。
解法：后序遍历 + 子树 ID
核心思路
两棵子树相同，当且仅当根值、左子树和右子树分别相同。于是可以给每种子树结构分配一个唯一整数 ID：
\[id(u)=ID\bigl(u.val,id(u.left),id(u.right)\bigr),\qquad id(null)=0\]三元组
(根值, 左子树 ID, 右子树 ID)相同，就从哈希表中复用同一个 ID；第一次见到的新三元组才分配新 ID。根据树高归纳，两个节点得到相同 ID，当且仅当它们的整棵子树相同。父节点依赖两个孩子的 ID，所以必须后序遍历。遍历时再统计每个 ID 的出现次数：计数从 1 变成 2 时加入当前节点，变成 3、4 时不再加入，恰好满足「同一种重复子树只返回一个代表」。
直接序列化成带空标记的字符串也能做对，但链状树会反复复制很长的子树字符串，最坏需要 $O(n^2)$ 时间和空间。整数 ID 将每个签名固定为三个整数，期望复杂度降为 $O(n)$，更适合作为面试主解法。
解题步骤
- 约定空节点 ID 为 0；准备
signatureToId、frequency和答案列表。- 后序递归当前节点，先取得左右孩子的 ID。
- 组成三元组
(node.val, leftId, rightId)。若哈希表已有该签名就复用 ID，否则分配新 ID。- 将该 ID 的出现次数加一；新次数恰好为 2 时，把当前节点加入答案。
- 向父节点返回当前子树 ID，整棵树遍历结束后返回答案。
以
root = [1,2,3,4,null,2,4,null,null,4]走一遍：这棵树的根是 1，左孩子 2 挂着左孩子 4；右孩子 3 挂着左孩子 2'（其左孩子是 4'）和右孩子 4''。第一个叶子 4 的签名是
(4,0,0)，分配 ID 1；其父节点 2 的签名是(2,1,0)，分配 ID 2。右侧的叶子 4' 再次得到 ID 1，频次变成 2，加入答案；右侧的节点 2' 再次得到 ID 2，也加入答案。最后一个叶子 4'' 让 ID 1 的频次变成 3，但不会重复加入。最终答案包含一棵[4]和一棵[2,4]。
代码实现
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class Solution {
private Map<List<Integer>, Integer> signatureToId;
private List<Integer> frequency;
private List<TreeNode> answer;
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
signatureToId = new HashMap<>();
frequency = new ArrayList<>();
frequency.add(0); // ID 0 留给空节点
answer = new ArrayList<>();
getId(root);
return answer;
}
private int getId(TreeNode node) {
if (node == null) {
return 0;
}
int leftId = getId(node.left);
int rightId = getId(node.right);
List<Integer> signature = List.of(node.val, leftId, rightId);
Integer id = signatureToId.get(signature);
if (id == null) {
id = signatureToId.size() + 1;
signatureToId.put(signature, id);
frequency.add(0);
}
int seen = frequency.get(id) + 1;
frequency.set(id, seen);
if (seen == 2) {
answer.add(node);
}
return id;
}
}
func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
signatureToID := make(map[[3]int]int)
frequency := []int{0} // ID 0 留给空节点
answer := make([]*TreeNode, 0)
var getID func(*TreeNode) int
getID = func(node *TreeNode) int {
if node == nil {
return 0
}
leftID := getID(node.Left)
rightID := getID(node.Right)
signature := [3]int{node.Val, leftID, rightID}
id, exists := signatureToID[signature]
if !exists {
id = len(signatureToID) + 1
signatureToID[signature] = id
frequency = append(frequency, 0)
}
frequency[id]++
if frequency[id] == 2 {
answer = append(answer, node)
}
return id
}
getID(root)
return answer
}
复杂度分析
- 时间复杂度：期望 $O(n)$。每个节点访问一次，对固定长度三元组做一次哈希查询与计数；哈希表操作期望 $O(1)$。
- 空间复杂度：$O(n)$。不同签名、频次数组和答案最多各保存 $O(n)$ 项，递归栈为 $O(h)$，其中 $h$ 是树高。
关键点总结
- 子树 ID 本质上是等价类编号：签名相同就复用 ID，不同签名才创建 ID。
- 签名必须同时包含根值、左 ID、右 ID；左右位置不可交换，空节点也必须有固定 ID。
- 依赖孩子信息构造父节点状态，是后序遍历的典型信号。
frequency[id] == 2精确捕捉第一次确认重复的时刻，天然保证每类只收一次。- 与完整字符串相比，固定长度整数签名避免了重复拷贝子树内容。
易错点总结
- 签名不含空节点或左右位置：
[1,2]与[1,null,2]会被错误地视为相同子树。- 只用节点值当键：值相同不代表其孩子结构相同，必须使用完整三元组。
- 父节点先于孩子编号：父签名依赖左右子树 ID，遍历顺序应是后序而不是前序。
- 每次遇到签名都创建新 ID：相同子树无法汇聚到同一个频次，必须先查表并复用已有 ID。
- 频次大于等于 2 就加入：同一子树出现 3 次会加入两次；只在
== 2时加入。- Java 用
int[]直接作哈希键：数组默认按对象身份比较，内容相同也可能查不到；应使用按内容实现相等性的不可变键。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 572. 另一棵树的子树 | 简单 | 单模式匹配，只需判断存在性 |
| 1367. 二叉树中的链表 | 中等 | 匹配对象是路径而非完整子树 |
| 面试题 04.10. 检查子树 | 中等 | 大树规模远超小树时的串匹配优化 |
| 297. 二叉树的序列化与反序列化 | 困难 | 序列化需可逆，还要实现反序列化 |