Поиск путей максимальной длины в бинарных деревьях

[Samir]

Вот возник вопрос. Как можно оптимальным образом найти путь максимальной длины в бинарном дереве. Пытался решить эту задачу так: искал максимальный путь, проходящий через корень дерева, а потом по доказанной мной теореме получалось, что корень пути максимальной длины дерева будет одной из вершин, принадлежащих тому максимальному пути, проходящему через корень дерева. Есть ли более лучший вариант решения этой задачи, и правильны ли мои рассуждения? Подскажите

[Cave]

Искать динамическим программированием по дереву: снизу вверх решать задачу для поддерева с корнем в данной вершине. Для этого легко заметить, что такой путь либо не проходит через корень - тогда он ищется среди детей, - либо проходит - тогда нужно знать две наиболее удалённые вершины. Это тоже легко поддерживать. Сложность, разумеется, получится $O(N)$, где $N$ - число вершин в графе.