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

Question

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

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

Answer 1

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

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