Почему это работает
- В полном дереве последний уровень заполняется слева. Если самый левый и самый правый пути одной длины, то и этот уровень заполнен, а в совершенном дереве из h уровней 2^h − 1 узлов.
- Если длины разные, хотя бы одно из двух поддеревьев совершенное, и один из двух вызовов отвечает сразу по своим краям. По частям считаем только вдоль одного пути вниз.
Сложность
Время O(log² n): по частям считаем вдоль одного пути из O(log n) вызовов, и каждый вызов проходит два края по O(log n) узлов. Память O(log n) на стек вызовов.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗