二叉树到二叉搜索树（BST）

Question

如何将二叉树转换为具有O（1）额外空间的二叉搜索树？

Answer 1

将一个无序的二叉树转换成一个有序的二叉搜索树是微不足道的，但要做的更快一点难度。

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

1. 抓斗从现有的树随机叶节点
2. 从现有的树
3. 取消链接的叶节点使节点新的二叉搜索树
4. 抓住从另一个随机叶节点所在的根目录现有树
5. 取消与该节点从现有的树
6. 查找正确的位置，并链接节点，到新的二叉搜索树
7. 重复步骤4-6，直到原来的树是空

你应该只需要几个变量，就像你解除链接的叶节点的父（除非节点具有父链接），根节点新树的结构和一些临时变量，全部在你的O（1）空间标准中。

这不会产生最佳的二叉搜索树。为此，您需要在添加节点之前对节点进行排序，然后按照正确的顺序添加它们，或者使用平衡二叉搜索树，如红黑树或松树树。

Answer 2

转换二叉树双链接列表 - 可以在O（n）的就地完成 在排序使用合并排序，nlogn 转换列表，背靠着树 - O（n）的

简单nlogn解。