二叉树到二叉树(BST)

Question

如何将二叉树转换为O(1)额外空间的二叉树？

Answer 1

将无序的二叉树转换成有序的二叉树很简单，但要快速完成就有点困难了。

这里有一个天真的实现，应该满足你的标准，我不会描述实际采取的步骤，只描述整体算法。

1. 从现有树中获取一个随机叶节点
2. 从现有树中取消链接该叶节点
3. 使该节点成为新的二进制搜索树的根
4. 从现有树中获取另一个随机叶节点

<代码>H19从现有树中取消该节点的链接<代码>H210<代码>H111找到正确的位置，并将该节点链接到新的二进制搜索树中<代码>H212<代码>H113重复步骤4-6，直到原始树为空<代码>H214<代码>G215

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

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

Answer 2

将二叉树转换为双向链表-可以在O(n)中就地完成，然后使用合并排序对其进行排序，nlogn将列表转换回树- O(n)

简单的nlogn解决方案。