Diameter of Binary Tree

Сначала разберёмся, как перемещаться по массиву. У узла с индексом i левый потомок находится по индексу 2*i+1, а правый — по индексу 2*i+2, поэтому его родитель находится по индексу (i-1)/2 с округлением вниз. Место считается занятым, только если его индекс находится в пределах массива, а значение в нём не равно -1. В массиве [8, 3, 6, 1, 4, -1, -1, -1, -1, 7] у узла 7 с индексом 9 родитель находится по индексу 4, а у узла 4 родитель находится по индексу 1.

Диаметр — это наибольшее расстояние между двумя узлами, поэтому можно измерить расстояние для каждой пары. Чтобы найти расстояние между индексами a и b, поднимайтесь к корню по одному шагу, пока пути не сойдутся, каждый раз начиная с большего индекса. Индекс большего значения никогда не находится на более высоком уровне, поэтому такой шаг не перескочит точку встречи. Число шагов равно числу рёбер. Для 9 и 2: узел 9 поднимается к 4, а затем к 1, узел 2 поднимается к 0, а узел 1 — к 0. Всего четыре шага.

Это верное решение, но оно медленное. Самый большой тест — полное дерево из 16383 узлов, что даёт примерно 1.3 × 10^8 пар, и для каждой пары требуется до 26 шагов. Миллиарды шагов для получения одного ответа — намного больше, чем позволяет лимит времени.

Посмотри на самый длинный путь от его самой высокой вершины — той вершины, где путь перестаёт идти вверх и начинает идти вниз. От неё путь проходит настолько далеко вниз по левой стороне, насколько возможно, и настолько далеко вниз по правой стороне, насколько возможно. Пусть height(c) считает количество вершин на самом длинном пути вниз от c, а для пустого места возвращает 0. Тогда самый длинный путь с поворотом в вершине i содержит height(2*i+1) + height(2*i+2) рёбер — по одному ребру на каждую из этих вершин.

Поэтому попробуй каждую вершину в качестве точки поворота и сохрани лучший результат. Во втором примере вершина 5 с индексом 1 имеет высоту 2 слева (1, 3) и 2 справа (9, 4), то есть путь из четырёх рёбер. У корня высота слева равна 3, а справа — 0, поэтому получается всего три ребра.

Каждый вызов height обходит целое поддерево, и вершина обходится повторно для каждого её предка, поэтому трудоёмкость составляет O(n·h). При h ≤ 14 этого здесь достаточно, но в дереве указателей в форме цепочки h может достигать n, и та же идея будет иметь трудоёмкость O(n²). Повторные вызовы height — это лишняя работа, от которой избавляет последний подход.

Высота узла зависит только от высот двух его потомков, и именно эти два числа нужны для проверки точки поворота. Поэтому вычислите их один раз, снизу вверх. При обходе в постфиксном порядке оба потомка обрабатываются раньше родителя. Затем в каждом узле у вас есть значения left и right: обновите ответ значением left + right, а родителю передайте 1 + max(left, right).

В первом примере лист 7 возвращает 1, расположенный выше него узел 4 возвращает 2, а узел 3 возвращает 3, поскольку его другой потомок 1 имеет высоту 1. Узел 6 возвращает 1. В корне left + right = 3 + 1 = 4 — это и есть ответ. Лучший результат, который может дать любой другой узел, — это 3, при 1 + 2 = 3.

Каждый узел посещается один раз, поэтому время выполнения составляет O(n), а глубина рекурсии равна глубине дерева — O(h), примерно один кадр на уровень. Ответ хранится в переменной вне рекурсии, потому что то, что возвращает вызов (высоту), — не то, что нужно в итоге (длину пути).