二叉樹到二叉搜索樹（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解。