Уровень в двоичном дереве с большинством узлов
Каков минимальный объем пространства, необходимый для определения того, какой уровень в двоичном дереве (случайный или BST) имеет наибольшее количество узлов?
2 ответа
Если вам разрешено уничтожить дерево, то вы можете преобразовать дерево в связанный список, выполняя bfs для дерева, по существу моделируя очередь с самим деревом!
Вы можете найти информацию об этом здесь: Преобразовать двоичное дерево в связанный список, сначала ширину, постоянное хранение / деструктивное
Это требует только O(1) пространство, как вы использовали узлы дерева.
O(1)
Пройдите BT (двоичное дерево) в подходе "поиск в ширину". Нажмите узлы с упоминанием уровня этого. Вы пройдете все узлы на уровне и перейдете на следующий уровень. Так что просто поддерживайте максимальную переменную и продолжайте обновлять ее.
Очередь (для BST) может занимать место в O(2^(log(n) -1)),