Постановка задачи :
Вам дано бинарное дерево. Возвращает количество уникальных поддеревьев в заданном бинарном дереве. В универсальных деревьях все узлы ниже корневого узла имеют то же значение, что и данные корня.
Входные данные состоят из значений узлов, разделенных одним пробелом в одной строке. Если узел нулевой, мы берем на его место -1.
Пример ввода:
1 2 3 2 -1 3 4 -1 -1 3 3 -1 -1 -1 -1 -1 -1
Пример вывода:
6
Подход :
Подход "снизу вверх"
В этом подходе мы будем подсчитывать количество универсальных поддеревьев восходящим образом. Это означает, что мы будем вычислять количество универсальных поддеревьев из левого и правого поддеревьев, а также вычислять, являются ли они сами универсальными или нет. Теперь для каждого посещаемого узла дерево с корнем в качестве текущего узла является уникальным тогда и только тогда, когда и левое, и правое поддерево являются уникальными, а значения левого и правого дочерних элементов (если существуют) также должны быть равны значению текущий узел. Поэтому, если эти условия выполнены, мы увеличим общее количество и вернем это значение и истинное логическое значение, чтобы обозначить количество уникальных узлов и то, что текущий узел также является уникальным. В противном случае мы вернем общее количество (без увеличения) с ложным логическим значением, обозначающим, что данное текущее поддерево не является уникальным.
Временная сложность: O(N)
Пространственная сложность: O(N)
Код :
Спасибо за чтение
Placewit воспитывает лучших инженеров, предоставляя интерактивные занятия в классе и помогая им развивать свои навыки и попадать в замечательные компании.
Узнайте больше на Placewit. Следите за нами в Instagram и Facebook для ежедневного обучения.
