Условие

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

Примеры

Для дерева ниже:

      1
     / \\\\
    2   3
   / \\\\
  4   5

Диаметр дерева равен 3. Длиннейший путь проходит через узлы 4, 2 и 5.

Для дерева ниже:

      1
     / \\\\
    2   3
   /
  4
 /
5

Диаметр дерева равен 4. Длиннейший путь проходит через узлы 5, 4, 2 и 3.

Решение

1. Найдем высоту каждого поддерева (количество ребер от корня до самого дальнего листа в поддереве). Это можно сделать с помощью обхода дерева в глубину (DFS).
2. Для каждого узла найдем максимальную сумму высот его двух поддеревьев. Это можно сделать, используя результаты шага 1.
3. Максимальная сумма высот двух поддеревьев для каждого узла - это диаметр поддерева с корнем в этом узле. Найдем максимальное значение среди всех узлов.
4. Максимальное значение, найденное на шаге 3, является диаметром всего дерева.

Пример

Рассмотрим дерево ниже:

      1
     / \\\\
    2   3
   / \\\\
  4   5

1. Высоты поддеревьев:

Высота поддерева с корнем в узле 1: 2
Высота поддерева с корнем в узле 2: 1
Высота поддерева с корнем в узле 3: 1
Высота поддерева с корнем в узле 4: 0
Высота поддерева с корнем в узле 5: 0

1. Максимальная сумма высот двух поддеревьев для каждого узла: