BST转换为对称结构树

Question

（我已经看过一些非常类似的练习，但它们都是常规的二叉树）。在标题中，我必须提出一种算法，将BST转换为另一个具有对称结构的BST，其中包含与前一个相同的值。例如

我的想法是从开始构建一棵新树。我将从一个新的根开始，该根将在原始树的有序值数组中处于原始对称的对称位置。在上面的示例中：3 5 6 7 12数字7将是新的根，因为它与前一个根5相比，在其左/右侧具有相反的节点数。但是它不能完全解决问题，因为新树取决于插入顺序。我想根据平衡进行旋转来结束它。我的问题是：这棵树必须是AVL树，所以我可以进行旋转（这意味着练习中有错误）。或者是否有更简单的方法来解决这个问题？

Answer 1

我会分两步解决这个问题：

1. 在每个节点中交换左右子指针。这将从左到右镜像树，反转所有值的顺序。
2. 从头开始执行前向有序遍历，从末尾执行向后有序遍历。进入锁定步骤，​​在前进和后退位置之间交换值，直到它们相遇。这将使值的顺序反转回原始顺序，同时保留新的树结构。