Учитывая корень двоичного дерева, вернуть все повторяющиеся поддеревья.

Для каждого типа повторяющихся поддеревьев вам нужно только вернуть корневой узел любого из них.

Два дерева дублируются, если они имеют одинаковую структуру с одинаковыми значениями узлов.

Ввод: корень = [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




Войти в полноэкранный режим

Выйти из полноэкранного режима