Поиск дублирующихся поддеревьев

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

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

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

Вход: root = [1,2,3,4,null,2,4,null,null,4].
Выходные данные: [[2,4],[4]]

Вход: root = [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




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

Оцените статью
devanswers.ru
Добавить комментарий