Преобразуйте двоичное дерево в двусвязный список, используя Morris Traversal

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

Получив двоичное дерево (BT), преобразуйте его в двусвязный список (DLL). Левый и правый указатели в узлах должны использоваться как предыдущий и следующий указатели соответственно в преобразованной DLL. Порядок узлов в DLL должен быть таким же, как в Inorder для данного двоичного дерева. Первый узел обхода Inorder должен быть головным узлом DLL.

Примеры:

Input: 
     1
   /  
  3    2
Output: 
Actual order: 3 1 2
Reverse order: 2 1 3
Explanation: The head of the linked list will be 3 and the last element will be 2.
DLL will be 3 <=> 1 <=> 2

Input:
           10
         /    
       20    30
     /      
    40  60
Output: 
Actual order: 40 20 60 10 30
Reverse order: 30 10 60 20 40

Ниже приведены несколько подходов, которые обсуждались ранее:

  • Преобразование заданного двоичного дерева в двусвязный список | Набор 1
  • Преобразование заданного двоичного дерева в двусвязный список | Набор 2
  • Преобразование заданного двоичного дерева в двусвязный список | Набор 3
  • Преобразование заданного двоичного дерева в двусвязный список | Набор 4

Подход:

The above approaches use recursion or stack to get the Inorder Traversal. This approach is based on Morris Traversal to find Inorder Traversalwhich is iterative and has a space complexity of O(1). 

The idea is that we will first create a singly linked list while doing Morris Traversal and later convert it into a doubly-linked list by setting the left pointer of every node to the previous node in inorder.  

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Выполните обход Морриса, чтобы пройти по дереву неупорядоченным образом за линейное время и создать односвязный список.
  • Теперь проходим по односвязному списку:
    • Создайте связь между текущим узлом и предшественником по порядку.
    • Обновляйте текущий и предыдущий (предшественник) узел соответственно на каждом шаге и переходите к следующему узлу.
  • Сгенерированный двусвязный список является искомым.

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

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

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