Правильный BST, два узла которого поменяны местами (используя Morris Traversal)

Опубликовано: 27 Февраля, 2023

Дано двоичное дерево поиска, в котором два узла двоичного дерева поиска (BST) поменялись местами. Задача состоит в том, чтобы исправить (или исправить) BST.
Примечание . У BST не будет дубликатов.

Примеры :

Input Tree:
         10
        /  
       5    8
      / 
     2   20

In the above tree, nodes 20 and 8 must be swapped to fix the tree.  
Following is the output tree
         10
        /  
       5    20
      / 
     2   8

Подход:

  • Пройдите BST по порядку и сохраните узлы в векторе.
  • Затем этот вектор сортируется после создания его копии.
  • Используйте сортировку вставками, поскольку она работает лучше всего и быстрее, когда массив почти отсортирован. Как и в этой задаче, только два элемента будут смещены, поэтому сортировка вставками здесь будет работать за линейное время.
  • После сортировки сравниваем отсортированный вектор и копию созданного ранее вектора, тем самым обнаруживаем ошибки-некоторые узлы и исправляем их, находя их в дереве и обменивая их.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N), где N — количество узлов в двоичном дереве.

Способ 2:

Чтобы понять это, вам нужно сначала понять Morris Traversal или Morris Threading Traversal. Он использует правый/левый указатель конечных узлов для достижения обхода пространства O (1) в двоичном дереве.

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

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ