Q
二叉查找樹的深度
0
A
回答
0
1)構建一個高度爲h
的完整二叉樹(h
是最小數字,例如2^h - 1
> =數組中元素的數量)。此時您可以忽略輸入數組。顯然,這棵樹具有最小深度(任何深度較小的樹都不能有足夠的節點來存儲所有數組元素)。
2)現在你可以使用簡單的遞歸方法填充這個數組元素:
i)填充左子樹。
ii)將最小的未使用號碼放入當前節點。
iii)填寫正確的子樹。
不要忘記在開始遍歷之前刪除2^h - 1 - n
樹葉(其中n
是輸入數組大小)(此步驟是必需的,因爲完整樹的大小爲2^h - 1
,但數組中只有n
個元素)。
一個O(n)
該算法的實現是非常有前途的(您可以明確地構建樹,刪除多餘的樹葉,然後遍歷它,因爲樹中的節點數爲O(n)
)。
+0
對於遲到的回覆感到抱歉,非常感謝你。你可以展示C函數對於上面的實現會是什麼樣子?我對c很陌生,而且在執行時遇到問題。 – overflow 2014-09-15 06:39:03
相關問題
- 1. 查找二叉樹的最大深度
- 2. 查找二叉查找樹的高度
- 3. 二叉搜索樹 - 查找高度和深度
- 4. 查找二叉樹中節點的深度不是BST
- 5. 查找二叉搜索樹的最小深度
- 6. 查找二叉樹
- 7. 二叉樹查找
- 8. 返回二叉查找樹的高度
- 9. 計算二叉搜索樹的深度?
- 10. 如何使用Prolog找到二叉樹的深度
- 11. 如何找到深度在列表中記述的二叉樹
- 12. 展平二叉查找樹
- 13. 查找二叉搜索樹中每個深度的節點數量
- 14. 無法找出二叉樹的高度
- 15. 二叉樹高度
- 16. 如何查找並返回二叉樹的最底部(最深節點)節點?二叉搜索樹?
- 17. 查找二叉樹的根值?
- 18. 查找二叉樹的邊框
- 19. 查找二叉樹中的節點
- 20. 二叉樹的深層副本
- 21. 二叉樹的長度
- 22. 大小爲1的二叉樹的最大深度
- 23. 在二進制搜索樹中查找數據點的深度
- 24. 在二叉樹中查找循環
- 25. 遞歸遍歷二叉查找樹
- 26. 使用二叉樹查找Anagrams
- 27. 使用Prolog查找二叉樹的高度
- 28. 查找樹的最大深度
- 29. 二叉搜索樹中的深度與距離
- 30. 給定深度的Swift二叉樹列表節點
你只需要找到深度,或者你需要找到樹? – 2014-09-12 15:00:41
@ AD.Net號碼它像日誌(array.length)(也許+1)。 – kraskevich 2014-09-12 15:30:55
@ user2040251,當然,謝謝。我只用6-7的數字,錯過了每個子數組的兩半 – 2014-09-12 15:40:01