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