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