Найдите два числа в двоичном дереве поиска, которое добавит до третьего номера

Question

Вам дается BST чисел. Вы должны найти в нем два числа (a, b) такие, что a + b = S, в O (n) время и O (1) пространство.

Какой может быть алгоритм?

Одним из возможных путей может быть два преобразование BST в двусвязном список, а затем начать с переднего и конца:

if front + end > S then end-- 

Или:

if front + end < S then front++ 

Answer 1

Как уже упоминалось, вы не можете решить эту проблему в постоянном пространстве O (1).Кроме того, во всех других предлагаемых в настоящее время решениях используется, по крайней мере, O (log^2 n) пространство, а не O (log n): стек имеет O (log n) кадры, и каждый кадр имеет указатель размера O (log n).

Теперь принятое решение от @ dharm0us уничтожает BST, преобразовывая его в массив. Это не нужно. Вместо этого используйте два итератора, один из которых выполняет обход в порядке и один выполняет обход обратного порядка, и ищите два числа так же, как и в массиве. Каждый итератор имеет стек с кадрами O (log n) с каждым фреймом, содержащим указатель размера O (log n) для общего пространства O (log^2 n). Время очевидно линейно O (n).

Answer 2

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

Метод, который вы ссылаетесь на , является a O(n) решение по временной сложности, но не с обычным двоичным деревом. Фактически, я очень подробно ответил на аналогичный вопрос here. Это было разрешено с помощью O(n), но только потому, что они не были первоначально отсортированы.

Это is Возможно с деревом, содержащим указатели родителей. Если дочерние узлы имеют указатели на своих родителей, вы можете в основном обрабатывать дерево как дважды связанный список, обработанный итеративно.

Для этого вы запускаете указатель начала вниз до самого левого узла, а конечный указатель - до самого верхнего узла. Вы также сохраняете две переменные, чтобы сохранить последнее движение (вверх или поперек, изначально вверх) каждого указателя, чтобы вы могли разумно выбрать следующий ход (front++ и end-- в своем вопросе).

Затем вы можете использовать текущие указатели и последние движения вместе с текущей суммой, чтобы определить, какой указатель перемещать (и как).

Answer 3

Мне был задан этот вопрос в недавнем интервью. Когда я застрял, мне дали намек.

Подсказка: предположим, что вам нужно решить эту же проблему для отсортированного массива, как бы вы тогда ее разрешили.

Me: Держите два указателя. Один в начале, другой в конце. Если сумма элементов в этих указателях меньше требуемой суммы, переместите указатель спереди вправо, иначе переместите указатель назад влево.

Интервьюер: Как вы могли бы сделать то же самое для двоичного дерева поиска?

Me: Выполняйте обход в порядке и сохраняйте указатели на узлы в массиве. И используйте ту же логику, что и в случае массивов.

Интервьюер: Да, это работает. Но сложность пространства O (n). Не могли бы вы его уменьшить?

Me (после долгого времени): Хорошо, конвертируйте BST в двунаправленный список, используя this algo. А затем используйте ту же логику, что и в случае массива. Косвенная сложность будет равна O (lg (n)) из-за рекурсии.