Учитывая root бинарного дерева, вернуть длину диаметра дерева.
Диаметр бинарного дерева – это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через root.
Длина пути между двумя узлами представлена количеством ребер между ними.
Пример 1:
Input: root = [1,2,3,4,5] Output: 3 Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
Решение:
В данной задаче нам нужно найти диаметр бинарного дерева.
Диаметр бинарного дерева – это максимальное расстояние между двумя узлами дерева, независимо от того, включает оно корневой узел или нет.
Итак, первая мысль, которая бросается в глаза, — это использовать метод обхода поиска в глубину для обхода всех узлов, потому что нам нужно пройти все узлы в глубину, чтобы найти самый длинный путь дерева.
Наш первый шаг — проверить, является ли дерево нулевым. Если да, вернуть 0.
if (!root)
return 0;
Мы создадим две переменные, left и right, для хранения глубины левого и правого поддеревьев соответственно.
int left = dfs(root -> left); int right = dfs(root -> right);
Теперь мы найдем максимальное расстояние между двумя узлами и сохраним его в переменной diameter.
Мы будем хранить максимальное значение диаметра и сумму левого и правого поддеревьев.
diameter = max(diameter, left + right);
Теперь мы вернем максимальный диаметр.
return max(left, right) + 1;
После всех этих действий вызовем функцию и получим необходимое значение диаметра.
Когда максимальный диаметр найден, наш последний шаг — сделать значение переменной diameter равным 0. Мы сделаем это, создав переменную закрытого класса.
private:
int diameter = 0;
Ниже приведена полная реализация задачи:
Спасибо за прочтение!
S.
