## 題解

### 使用哈希表映射減少字串拼接時間複雜度

# 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]]:
        hashMap = {}
        counts = {}
        output = []
        def dfs(root):
            if not root:
                return 0 
            subTrees = f"{dfs(root.left)},{root.val},{dfs(root.right)}"
            id = 0
            if subTrees not in hashMap:
                id = len(counts) + 1
                hashMap[subTrees] = id
                counts[id] = 1
            else:
                id = hashMap[subTrees]
                counts[id] += 1
            if counts[id] == 2:
                output.append(root)
            return id
        dfs(root)
        return output