Напишите функцию, которая принимает двоичное дерево и возвращает его диаметр.
Диаметр бинарного дерева определяется как длина самого длинного пути, даже если этот путь не проходит через корень дерева.
Длина пути – это количество ребер между первым узлом пути и его последним узлом.
Мы будем использовать поиск в глубину для обхода каждого узла входного двоичного дерева.
Каждый узел содержит две информации: текущий диаметр и текущую высоту.
Зная Высоту и дочерние диаметры, мы можем рассчитать диаметр текущего узла.
Текущий диаметр = MAX(левый диаметр, правый диаметр, длина самого длинного пути)
Наш базовый случай рекурсии — это (0,0) текущая высота и текущий диаметр, так как мы достигли дочернего элемента None.
Мы отслеживаем родительские узлы в стеке вызовов и, поднимаясь обратно, обновляем информацию о текущем диаметре и текущей высоте для каждого узла.
Мы создали структуру для хранения текущего диаметра и текущей высоты узла.
Код доступен здесь.
Временная сложность составляет O(n), поскольку мы проходим через каждый узел входного дерева.
Сложность пространства составляет O(d), так как мы можем хранить длину самой длинной ветви (d) во входном дереве в нашем стеке вызовов.
