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