C++如何在不使用额外空间的情况下将二叉树转换为二叉搜索树

Question

这个 C++ 作业要求我们创建一个二叉树并检查它是否是一个二叉搜索树。如果不是，那么我们需要一种算法来修复它而不使用额外的空间或其他数据结构。我和我的 friend 们都在寻找一个合适的算法，因为大量的在线搜索几乎没有结果。我们不太关心运行时间，我们主要专注于弄清楚如何根据给定的要求修复 BT。

链表用于创建树，但我们对如何实现某种算法将其转换为 BST 感到困惑。

如有任何提示，我们将不胜感激!

Answer 1

按照下面给出的步骤:

1. 检查您的二叉树 T1 是否为二叉搜索树。如果是，不用担心，否则转到步骤 2
2. 对给定的二叉树进行后序遍历并创建另一棵树T2(将其视为初始指向NULL的二叉搜索树，表示为空最初)。
3. 在对二叉树进行后序遍历的同时，继续逐一删除节点，并为每个节点创建一个拷贝，然后将该节点逐一插入到 BST T2 中。 (注意:插入应以 BST 方式完成)

复杂性:
最坏时间复杂度:O(n²)。
空间复杂度:O(1)。 常量