难度: Medium
给你一棵二叉树的根节点 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运行时间: 32 ms
内存: 17.9 MB
# 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(node):
if not node: return 0
tri = (node.val, dfs(node.left), dfs(node.right))
if tri not in seen:
nonlocal idx
idx += 1
seen[tri] = (node, idx)
return idx
else:
(n, i) = seen[tri]
output.add(n)
return i
output = set()
seen = collections.defaultdict(list)
idx = 0
dfs(root)
return list(output)
这个题解使用了深度优先搜索（DFS）和哈希表来查找重复的子树。主要思路如下： 1. 定义一个DFS函数，用于遍历二叉树的每个节点。 2. 对于每个节点，创建一个元组 `(node.val, dfs(node.left), dfs(node.right))`，表示以该节点为根的子树的结构。 3. 使用哈希表 `seen` 存储已遍历过的子树结构。如果当前子树结构已经在哈希表中出现过，说明找到了一个重复的子树，将其加入到输出集合 `output` 中。 4. 为了区分不同的子树结构，使用一个递增的索引 `idx`，为每个新的子树结构分配一个唯一的索引。 5. 最后返回输出集合 `output` 中的所有重复子树的根节点。
时间复杂度: O(n)
空间复杂度: O(n)
```python
# 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(node):
if not node: return 0
# 创建表示以当前节点为根的子树结构的元组
tri = (node.val, dfs(node.left), dfs(node.right))
if tri not in seen:
nonlocal idx
idx += 1
seen[tri] = (node, idx)
return idx
else:
(n, i) = seen[tri]
output.add(n)
return i
output = set() # 存储重复子树的根节点
seen = collections.defaultdict(list) # 存储已遍历过的子树结构
idx = 0 # 用于给新的子树结构分配唯一索引
dfs(root) # 执行深度优先搜索
return list(output)
```
在题解中，每个子树的结构通过一个元组(tri)来表示，这个元组包含了当前节点的值、左子树的索引和右子树的索引。因此，即使两个子树在结构上看似相同，如果它们的节点值不同，它们的元组表示也会不同。例如，对于节点值不同的两个子树，即使它们的子树结构相同，由于节点值的不同，生成的元组也会不同，从而使得这两个子树可以被区分开来。
在题解中，元组(tri)的唯一性是通过包含三个关键信息来实现的：当前节点的值、左子节点的递归调用返回的索引和右子节点的递归调用返回的索引。索引是基于子树结构递归定义的，意味着即便两个子树在结构上相似，如果它们的任何一个子节点不同（包括值和子树结构），递归调用返回的索引也会不同。这种方法通过深度优先搜索确保了每一个独特的子树结构在哈希表中都有一个唯一的代表，从而保证了元组的唯一性。
索引idx在算法中起到了为每个独特的子树结构分配一个唯一标识符的作用。这个标识符用于在哈希表中存储和检索子树结构，使得我们能够快速判断一个子树是否在之前已经出现过。尽管在某些实现中可以通过直接使用子树结构的序列化字符串作为键来省略这个索引，但使用索引可以减少哈希表中字符串的存储需求，并可能提高效率。因此，这个索引虽然理论上可以省略，但在实践中有其具体的优势。
是的，输出集合output使用set数据结构意味着其中存储的元素是唯一的。在本题解中，如果二叉树中存在多个相同的子树结构，即使这些结构来自不同的位置，set将只保存它们的一个代表节点。这样做的目的是确保找到的每一个重复子树只被记录一次，从而避免重复输出相同的子树根节点。