Создайте волновой массив из данного двоичного дерева поиска

Учитывая двоичное дерево поиска, задача состоит в том, чтобы создать волновой массив из заданного двоичного дерева поиска. Массив arr[0..n-1] называется волновым массивом, если arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= …

Примеры:

Input:

Output: 4 2 8 6 12 10 14
Explanation: The above mentioned array {4, 2, 8, 6, 12, 10, 14} is one of the many valid wave arrays.

Input:

Output: 4 2 8 6 12 

Подход: Данную проблему можно решить, заметив, что неупорядоченный обход бинарного дерева поиска дает узлы в неубывающем порядке. Поэтому сохраните неупорядоченный обход данного дерева в вектор. Поскольку вектор содержит элементы в отсортированном порядке, его можно преобразовать в волновой массив, заменив соседние элементы на все элементы в диапазоне [0, N), используя подход, обсуждаемый в этой статье.

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

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