В чем проблема:восстановить двухэлементное бинарное дерево поиска
Два элемента двоичного дерева поиска (BST) заменяются по ошибке. Восстановите дерево, не изменяя его структуру.
Мое решение хранит указатель на узел в массиве во время обхода порядка. Затем пересечь массив, чтобы найти два пропущенных узла, изменить их значения. Но мне нужно O (n) пространство для выделения массива. Мой вопрос в том, могу ли я решить его с постоянным пространством?
Вам не нужно хранить элементы в массиве. Когда два элемента обмениваются местами, один из них перемещается в более раннюю позицию, поэтому он больше, чем элемент, выполняющий его в обходном пути. Вам не нужно сохранять элементы в массиве, чтобы найти это - вам нужно сохранить только один из предыдущих узлов. Аналогично, для элемента, перемещенного вправо, он будет меньше, чем предшествующий ему элемент, поэтому вы можете снова найти его с сохранением того же контекста (1 предшествующий элемент). Как вы предположили, одного обходного ордера достаточно, чтобы найти неуместные элементы.