Сложность: easy
Учитывая корень бинарного дерева, вернуть длину диаметра дерева.
Диаметр бинарного дерева — это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень.
Длина пути между двумя узлами представлена числом ребер между ними.
Пример:
Input: root = [1,2]
Output: 1
👨💻 Алгоритм:
1⃣Инициализируйте целочисленную переменную diameter для отслеживания самого длинного пути, найденного с помощью DFS.
2⃣Реализуйте рекурсивную функцию longestPath, которая принимает TreeNode в качестве входных данных и рекурсивно исследует дерево: Если узел равен None, вернуть 0. Рекурсивно исследовать левые и правые дочерние узлы, возвращая длины путей leftPath и rightPath. Если сумма leftPath и rightPath больше текущего diameter, обновить diameter. Вернуть большее из leftPath и rightPath плюс 1.
3⃣Вызвать longestPath с root.
😎 Решение:
class Solution:
def __init__(self):
self.diameter = 0
def diameterOfBinaryTree(self, root):
self.diameter = 0
self.longestPath(root)
return self.diameter
def longestPath(self, node):
if not node:
return 0
leftPath = self.longestPath(node.left)
rightPath = self.longestPath(node.right)
self.diameter = max(self.diameter, leftPath + rightPath)
return max(leftPath, rightPath) + 1
Ставь 👍 и забирай 📚 Базу знаний