题目
给定一棵二叉树 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,10^4]范围内。
-200 <= Node.val <= 200
思路
先想的是如何存放这个树，但是半天没想出来，借鉴了官方的做法，使用dfs将树的每个节点的子树序列化为 根节点(左子树)（右子树）的字符串形式并存在哈希表中，若发现哈希表中有该序列，则为重复的子树。
题解
class Solution: def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]: def dfs(node: Optional[TreeNode]) -> str: # 空树返回空字符串 if not node: return "" # 序列化特定形式 serial = "".join([str(node.val), "(", dfs(node.left), ")(", dfs(node.right), ")"]) # 判重 if seen.get(serial): tree = seen.get(serial) repeat.add(tree) else: seen[serial] = node return serial seen = dict() repeat = set() dfs(root) return list(repeat)
