Convert Sorted Array to Binary Search Tree

Лёгкая№108построить дерево

Дан массив чисел, отсортированный по возрастанию. Нужно построить из всех них двоичное дерево поиска, сбалансированное по высоте: в каждом узле высоты двух поддеревьев отличаются не больше чем на один. Подойдёт любое такое дерево. Наш массив: [-7, -2, 0, 3, 8, 11] — один из ответов по уровням: [0, -7, 8, none, -2, 3, 11].

108 Convert Sorted Array to Binary Search TreeРазбор · 1×

Пример: построить сбалансированное дерево поиска из отсортированного массива [-7, -2, 0, 3, 8, 11]: середина — корень, половины — поддеревья.

0-71-2203348511
ещё не в дереведиапазон текущего вызовасередина: текущий узелждёт поддеревоподдерево готово

Строим дерево из всего массива: build(0, 5)

01/47
сначала · назад · пуск · шаг
Скорость
1function sortedArrayToBST(nums):
2 return build(0, len(nums) - 1)
3
4function build(lo, hi):
5 if lo > hi:
6 return none
7 mid = (lo + hi) / 2 // rounded down
8 node = new node(nums[mid])
9 node.left = build(lo, mid - 1)
10 node.right = build(mid + 1, hi)
11 return node
состояние
lo
–
hi
–
mid
–
node
–
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Всё левее середины меньше неё, а всё правее — больше, поэтому середина в корне и половины под ней дают дерево поиска; то же верно внутри каждой половины.
  2. Половины отличаются по размеру не больше чем на одно значение, поэтому и высоты их деревьев — не больше чем на один: всё дерево сбалансировано.
  3. При чётном количестве подходит любая из двух середин; округление вниз просто отдаёт лишнее значение правой стороне, как у -7 и -2.

Сложность

Время O(n): каждое значение один раз становится узлом, а вызов кроме двух вызовов делает O(1) работы. Память O(log n) сверх самого дерева: стек вызовов глубиной в высоту сбалансированного дерева.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.