Уровень в бинарном дереве с большим количеством узлов

Question

Что такое количество минимального пространства необходимо выяснить, какой уровень в бинарном дереве (случайного или BST) имеет наибольшее количества узлов?

Answer 1

O(1)

Траверс BT (Binary Tree) вширь-First-Search подход. Нажмите узлы с указанием уровня. Вы пройдете все узлы уровня и перейдете на следующий уровень. Поэтому просто поддерживайте максимальную переменную и продолжайте ее обновлять.

Очередь (для BST) может занимать место в O(2^(log(n) -1)).

Answer 2

Если вам разрешено уничтожить дерево, вы можете преобразовать дерево в связанный список, выполняя bfs дерева, в основном имитируя очередь с самим деревом!

Вы можете найти информацию о том, что здесь: Convert a binary tree to linked list, breadth first, constant storage/destructive

Для этого требуется лишь O(1) пространство, как вы повторно использовали узлы дерева.