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