在算法面试中，二叉树相关问题一直是考查重点，而LeetCode第652题“寻找重复子树”（Find Duplicate Subtrees）更是其中的经典题。这道题不仅要求识别树结构中的重复模式，还要求以列表形式返回所有重复子树的根节点。很多初学者在实现时容易卡在一个关键细节上：根节点究竟在何时、以何种方式被加入结果列表？ 本文将从问题本质出发，结合序列化与哈希表方法，深入拆解这一核心步骤。
一、问题回顾
给定一棵二叉树，找出所有结构相同、节点值相同的子树（子树包含其所有后代节点），并将这些重复子树的根节点存入一个列表返回。例如，一棵树中若存在两棵完全相同的子树，则它们的根节点都应被加入结果。注意，如果同一子树出现三次以上，仍只应被记录一次（即每个重复子树仅需一个根节点代表）。
二、常见解法：序列化 + 哈希表
绝大多数高效解法采用“序列化 + 哈希表”的思路。其核心理念是：为每个子树生成一个能唯一标识其结构及节点值的字符串（或编码），然后利用哈希表统计每种字符串出现的次数。当某字符串第二次出现时，就将当前子树的根节点加入结果列表。为什么是第二次，而不是第一次？ 因为第一次出现时，我们尚不知道它是否会重复；等到第二次出现时，才确认它是重复的，此时加入根节点恰好避免重复添加同一组节点。
三、根节点加入列表的时机与方式
以最常见的后序遍历序列化为例。我们采用递归函数 serialize(node)，若节点为空则返回 "#"；若不为空，则递归处理左、右子树，组合成 str(node.val) + "," + leftStr + "," + rightStr。关键在于：哈希表 map 记录的是序列化字符串与第一次出现的根节点的映射，同时可能维护一个计数器。
伪代码如下：
def findDuplicateSubtrees(root):
map = {} # 序列化字符串 -> 第一次出现的根节点（或计数器）
res = []
def dfs(node):
if not node:
return "#"
left = dfs(node.left)
right = dfs(node.right)
s = f"{node.val},{left},{right}"
if s in map:
# 若已存在且当前节点尚未被记录，则加入结果
if map[s] is not None: # 或使用计数器：若计数为1则加入
res.append(node)
map[s] = None # 标记已处理，防止后续根节点被重复加入
else:
map[s] = node # 第一次出现：记录节点
return s
dfs(root)
return res
注意这段代码中的细节：当第一次遇到某序列化字符串时，将其对应的根节点存入 map；当第二次遇到时，将当前节点（即第二个重复子树的根）加入 res，并将 map[s] 置为 None 或增加一个已处理标记，这样后续第三次、第四次出现时就不会再重复添加。这一机制保证了每个重复子树只会被加入一次，并且加入的是第二个出现的根节点（或更严谨地说，是任意一个重复子树的根节点，只要保证唯一即可）。有些实现会选择在第一次出现时保留节点，第二次出现时将第一次的节点加入结果，之后再遇到不再处理——两种方式本质相同，区别在于返回的是第一次还是第二次的根。
本题的标题“How the root object is added to the list”正是指这一逻辑。很多初学者容易错误地：在第一次出现时就将节点加入结果，或者在每次出现时都加入，导致重复或遗漏。
四、为什么选择后序遍历？
序列化必须保证能够唯一还原子树，因此需要包含空节点标记。前序、中序、后序都可以，但后序在处理上更自然：先处理子节点，再组合父节点，符合递归的栈顺序。前序或中序同样可行，但需注意：如果只使用节点值前后顺序而不加入空标记，不同结构的子树可能产生相同序列（例如左斜树和右斜树的值序列可能相同），因此必须显式标记 null。LeetCode的官方题解多采用后序+"#"来表示空。
五、复杂度和扩展
- 时间复杂度：O(n)，每个节点访问一次，字符串拼接可能涉及复制，但通过使用整数ID（如将每个子树映射为数字）可优化到O(n)。
- 空间复杂度：O(n)，递归栈和哈希表。
此题还有另一种解法——使用三元组（值，左子树ID，右子树ID）进行哈希，本质上与序列化异曲同工，但避免了字符串拼接的开销，更高效。
六、小结
LeetCode 652 看似简单，却巧妙地将序列化、哈希、递归与结果收集融为一体。理解“根节点加入列表”的时机是解出本题的关键：第二次出现时加入，且只加入一次。这一模式也常见于其他“寻找重复”类问题，如数组中的重复元素、重复文件等。掌握它，不仅有助于面试，更能提升对数据结构唯一标识与计数的抽象思维。
下次当你刷到这道题时，不妨多问自己一句：我是如何把 root object 加到 list 里的？并且，为什么是现在？