Обход двоичного дерева по часовой стрелке | Комплект - 2

Учитывая двоичное дерево. Задача состоит в том, чтобы напечатать круговой обход по часовой стрелке по спирали заданного двоичного дерева.

Примеры:

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

Вход :
           20
         / 
        8 22
      /  / 
     5 3 4 25
          / 
         10 14
Выход: 20 14 10 8 22 25 4 3 5

Мы уже обсуждали обход двоичного дерева по часовой стрелке с использованием 2D-массива. Здесь мы обсудим другой подход, который не будет использовать 2D-массив.

Подход: идея состоит в том, чтобы использовать две переменные i, инициализированные значением 1 и j, инициализированные высотой дерева, и запустить цикл while, который не прерывается, пока i не станет больше j. Мы будем использовать другую переменную flag и инициализировать ее значением 0. Теперь в цикле while мы проверим условие: если flag равен 0, мы будем обходить дерево слева направо и помечать флаг как 1, чтобы в следующий раз пройти через tree справа налево, а затем увеличиваем значение i, чтобы в следующий раз мы посетили уровень чуть ниже текущего уровня. Также, когда мы будем проходить уровень снизу, мы отметим флаг как 0, чтобы в следующий раз пройти по дереву справа налево, а затем уменьшить значение j, чтобы в следующий раз мы посетили уровень чуть выше текущего уровня. Повторяйте весь процесс до тех пор, пока двоичное дерево не будет полностью пройдено.

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

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

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