data-structures - 二叉树到二叉搜索树 (BST)

Question

如何使用 O(1) 额外空间将二叉树转换为二叉搜索树？

Answer 1

将无序二叉树转换为有序二叉搜索树很简单，但要快速完成有点困难。

这是一个应该满足您的标准的简单实现，我不会描述要采取的实际步骤，只是描述整体算法。

1. 从现有树中获取随机叶节点
2. 取消叶节点与现有树的链接
3. 使该节点成为新二叉搜索树的根
4. 从现有树中获取另一个随机叶节点
5. 取消该节点与现有树的链接
6. 找到正确的位置并将节点链接到新的二叉搜索树中
7. 重复步骤4-6，直到原始树为空

您应该只需要几个变量，例如要取消链接的叶节点的父节点(除非该节点具有父链接)、新树的根节点以及几个临时变量，所有这些都在您的O(1) 空间标准。

这不会产生最佳的二叉搜索树。为此，您需要在添加节点之前对节点进行排序，并以正确的顺序添加它们，或者使用平衡二叉搜索树，例如红黑树或伸展树(Splay Tree)。