如何将二叉树转换为具有 O(1) 额外空间的二叉搜索树？
问问题
1669 次
2 回答
7
将无序二叉树转换为有序二叉搜索树很简单，但要快速完成有点困难。
这是一个幼稚的实现，应该满足您的标准，我不会描述要采取的实际步骤，只描述整体算法。
- 从现有树中获取随机叶节点
- 从现有树中取消叶节点的链接
- 使节点成为新二叉搜索树的根
- 从现有树中获取另一个随机叶节点
- 从现有树中取消该节点的链接
- 找到合适的位置并将节点链接到新的二叉搜索树中
- 重复步骤 4-6，直到原始树为空
您应该只需要几个变量，例如要取消链接的叶节点的父节点（除非节点具有父链接）、新树的根节点和几个临时变量，所有这些都在您的 O(1 ) 空间标准。
这不会产生最佳的二叉搜索树。为此，您需要在添加节点之前对节点进行排序，并以正确的顺序添加它们，或者使用平衡二叉搜索树，如红黑树或展开树。
于 2010-05-17T10:24:22.813 回答
-1
将二叉树转换为双向链表 - 可以在 O(n) 中就地完成然后使用归并排序，nlogn 将列表转换回树 - O(n)
简单的 nlogn 解决方案。
于 2014-02-18T19:52:15.133 回答