Предварительный заказ, почтовый заказ и порядок обхода двоичного дерева за один проход | (Используя рекурсию)

Для заданного бинарного дерева задача состоит в том, чтобы напечатать все узлы бинарного дерева в предварительном порядке, после заказа и в порядке за одну итерацию.

Примеры:

Input: 

 

Output: 
Pre Order:  1 2 4 5 3 6 7 
Post Order:  4 5 2 6 7 3 1 
In Order:    4 2 5 1 6 3 7

Input:  

 

Output: 
Pre Order: 1 2 4 8 12 5 9 3 6 7 10 11 
Post Order: 12 8 4 9 5 2 6 10 11 7 3 1 
In Order: 8 12 4 2 9 5 1 6 3 10 7 11 

Подход: в этой статье представлено итеративное решение этой проблемы. Здесь этот подход основан на концепции рекурсии.

The idea is to place the recursive calls properly as it is done for each of the inorder, preorder and postorder traversal.

Выполните шаги, указанные ниже, чтобы решить проблему.

• Создайте 3 массива для хранения обхода по порядку, предварительному и обратному порядку.
• Вставьте текущий узел в массив предварительного заказа и вызовите функцию рекурсии для левого дочернего элемента .
• Теперь поместите текущий узел в неупорядоченный массив и сделайте рекурсивный вызов для правого дочернего элемента (правого поддерева).
• Посетите данные текущего узла в массиве постпорядка перед выходом из текущей рекурсии.

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

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