LeetCode 题解工作台
寻找重复的子树
给你一棵二叉树的根节点 root ，返回所有 重复的子树 。 对于同一类的重复子树，你只需要返回其中任意 一棵 的根结点即可。 如果两棵树具有 相同的结构 和 相同的结点值 ，则认为二者是 重复 的。 示例 1： 输入： root = [1,2,3,4,null,2,4,null,null,4] 输…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
后序遍历，序列化每个子树，用哈希表判断序列化的字符串出现次数是否等于 `2`，若是，说明这棵子树重复。 class Solution:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵二叉树的根节点 root ，返回所有 重复的子树 。
对于同一类的重复子树，你只需要返回其中任意 一棵 的根结点即可。
如果两棵树具有 相同的结构 和 相同的结点值 ，则认为二者是 重复 的。
示例 1：
输入：root = [1,2,3,4,null,2,4,null,null,4] 输出：[[2,4],[4]]
示例 2：
输入：root = [2,1,1] 输出：[[1]]
示例 3：
输入：root = [2,2,2,3,null,3,null] 输出：[[2,3],[3]]
提示：
- 树中的结点数在
[1, 5000]范围内。 -200 <= Node.val <= 200
解题思路
方法一：后序遍历
后序遍历，序列化每个子树，用哈希表判断序列化的字符串出现次数是否等于 2，若是，说明这棵子树重复。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findDuplicateSubtrees(
self, root: Optional[TreeNode]
) -> List[Optional[TreeNode]]:
def dfs(root):
if root is None:
return '#'
v = f'{root.val},{dfs(root.left)},{dfs(root.right)}'
counter[v] += 1
if counter[v] == 2:
ans.append(root)
return v
ans = []
counter = Counter()
dfs(root)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N), where N is the number of nodes, since each node is visited once and subtree serialization is proportional to its size. Space complexity is O(N) for the hash map storing subtree serializations and the recursion stack in DFS. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask candidates how to represent subtrees uniquely to detect duplicates efficiently.
- question_mark
Probe understanding of DFS traversal order and why post-order is suitable for subtree serialization.
- question_mark
Check if the candidate considers memory optimization when multiple identical subtrees exist.
常见陷阱
外企场景- error
Serializing subtrees incorrectly by ignoring null nodes, which can cause false positives.
- error
Adding duplicate roots multiple times instead of tracking counts properly.
- error
Using inefficient traversal orders or repeated recomputation of subtree serializations.
进阶变体
外企场景- arrow_right_alt
Find duplicate subtrees but return all occurrences instead of only one root per duplicate type.
- arrow_right_alt
Detect duplicate subtrees in an n-ary tree using a similar DFS and hash map approach.
- arrow_right_alt
Return the count of duplicate subtree types rather than the root nodes.