Преобразование BST в дерево симметричной структуры

Question

(Я видел несколько очень похожих упражнений, но все они для обычных бинарных деревьев). Как и в заголовке, я должен предложить алгоритм для преобразования BST в другой BST с симметричной структурой, который включает в себя те же значения, что и предыдущий. Например

Моя идея состояла в том, чтобы построить новое дерево с самого начала. Я бы начал с нового корня, который был бы в симметричной позиции исходного в отсортированном массиве значений из исходного дерева. В приведенном выше примере: 3 5 6 7 12 число 7 будет новым корнем, потому что он перевернул число узлов на левой / правой стороне по сравнению с предыдущим корнем 5. Но это не решает проблему полностью, потому что новое дерево зависит от порядка вставки. Я хотел покончить с выполнением поворотов в зависимости от баланса. Мой вопрос: должно ли это дерево быть деревом AVL, чтобы я мог выполнять повороты (это означало бы, что в упражнении есть ошибка). Или есть и более простой способ решить это?

Answer 1

Я бы решил эту проблему в два этапа:

1. Поменяйте местами левый и правый дочерние указатели в каждом узле. Это будет отражать дерево слева направо, изменяя порядок всех значений.
2. Выполните прямой упорядоченный обход с начала и обратный упорядоченный обход с конца. Перейдите к шагу блокировки, меняя значения между положениями вперед и назад, пока они не встретятся. Это обратит порядок значений обратно к их первоначальному порядку, сохраняя новую древовидную структуру.