给定一棵二叉树
root
,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。
如果两棵树具有相同的结构和相同的结点值,则它们是重复的。
输入:root = [1,2,3,4,null,2,4,null,null,4]
输出:[[2,4],[4]]
输入:root = [2,1,1]
输出:[[1]]
输入:root = [2,2,2,3,null,3,null]
输出:[[2,3],[3]]
提示:
- 树中的结点数在
[1,10^4]
范围内。-200 <= Node.val <= 200
将每一棵子树都「序列化」成一个字符串,并且保证:
只要使用一个哈希表存储所有子树的序列化结果,如果某一个结果出现了超过一次,我们就发现了一类重复子树。
# 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]]:
visited, result = {}, []
def dfs(root: Optional[TreeNode]) -> str:
if not root:
return ""
serial = "#".join((str(root.val), dfs(root.left), dfs(root.right)))
if serial not in visited:
visited[serial] = 1
else:
visited[serial] += 1
if visited[serial] == 2:
result.append(root)
return serial
dfs(root)
return result
复杂度分析:
- 时间复杂度: O(n^2), 序列化的代价是 O(n),遍历的代价是 O(n)
- 空间复杂度: O(n^2)