Найдите два числа в двоичном дереве поиска, которые складываются в третье число

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 (n). Не могли бы вы уменьшить его?

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

Answer 2

Как уже упоминалось, вы не можете решить эту проблему в постоянном пространстве 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 3

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

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

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

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

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