二叉查找樹的深度

Question

給定一個有序排列的數組寫一個程序來找到一個深度最小的二叉搜索樹，那麼深度是多少？

我知道如何將數組轉換爲平衡BST，但是如何使函數創建最小深度的BST？

Answer 1

1）構建一個高度爲h的完整二叉樹（h是最小數字，例如2^h - 1> =數組中元素的數量）。此時您可以忽略輸入數組。顯然，這棵樹具有最小深度（任何深度較小的樹都不能有足夠的節點來存儲所有數組元素）。

2）現在你可以使用簡單的遞歸方法填充這個數組元素：
i）填充左子樹。
ii）將最小的未使用號碼放入當前節點。
iii）填寫正確的子樹。
不要忘記在開始遍歷之前刪除2^h - 1 - n樹葉（其中n是輸入數組大小）（此步驟是必需的，因爲完整樹的大小爲2^h - 1，但數組中只有n個元素）。

一個O(n)該算法的實現是非常有前途的（您可以明確地構建樹，刪除多餘的樹葉，然後遍歷它，因爲樹中的節點數爲O(n)）。