Find Duplicate Subtrees LeetCode solution in Python

1
class Solution:
2
    def findDuplicateSubtrees(
3
        self, root: Optional[TreeNode]
4
    ) -> List[Optional[TreeNode]]:
5
        ans = []
6
        path_map = {}
7

8
        def dfs(node):
9
            if not node:
10
                return "#"
11

12
            path = ",".join([str(node.val), dfs(node.left), dfs(node.right)])
13

14
            if path in path_map:
15
                path_map[path] += 1
16
                if path_map[path] == 2:
17
                    ans.append(node)
18
            else:
19
                path_map[path] = 1
20

21
            return path
22

23
        dfs(root)
24
        return ans