Свести BST в отсортированный список | По убыванию

Учитывая двоичное дерево поиска, задача состоит в том, чтобы свести его к отсортированному списку в порядке убывания. Точнее, значение каждого узла должно быть больше, чем значения всех узлов справа, а его левый узел должен иметь значение NULL после выравнивания. Мы должны сделать это в дополнительном пространстве O (H), где H - высота BST.

Примеры:

 Вход: 
          5 
        /  
       3 7 
      /  /  
     2 4 6 8
Выход: 8 7 6 5 4 3 2

Вход:
      1
       
        2
         
          3
           
            4
             
              5
Выход: 5 4 3 2 1

Подход: простой подход состоит в том, чтобы воссоздать BST из его обхода «в обратном порядке». Это займет O (N) дополнительного места, где N - количество узлов в BST.
Чтобы улучшить это, мы будем моделировать обратный обход двоичного дерева по порядку следующим образом:

1. Создайте фиктивный узел.
2. Создайте переменную с именем «prev» и сделайте так, чтобы она указывала на фиктивный узел.
3. Выполняйте обратный обход по порядку и на каждом шаге.
   • Установить предыдущий -> правый = текущий
   • Установить предыдущий -> слева = NULL
   • Установить prev = curr

Это улучшит сложность пространства до O (H) в худшем случае, поскольку обход по порядку занимает O (H) дополнительного пространства.

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

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.