중복 하위 트리 찾기

이진 트리의 루트가 주어지면 모든 중복 하위 트리를 반환합니다.

각 종류의 중복 하위 트리에 대해 그 중 하나의 루트 노드만 반환하면 됩니다.

두 트리가 동일한 노드 값을 가진 동일한 구조를 갖는 경우 두 트리가 중복됩니다.

입력: 루트 = [1,2,3,4,null,2,4,null,null,4]
출력: [[2,4],[4]]

입력: 루트 = [2,1,1]
출력: [[1]]

class Solution:
    def dfs(self, node, d):
        if not node:
            return 'N'
        l, r = self.dfs(node.left, d), self.dfs(node.right, d)
        path = str(node.val) + '-' + l + '-' + r

        if path in d:
            d[path] += 1
            if d[path] == 2:
                self.res.append(node)
        else:
            d[path] = 1
        return path

    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        self.res = []
        self.dfs(root, dict())
        return self.res