0
給定二叉搜索樹（BST）。迭代查找二叉查找樹的最大深度。尋找二元搜索樹（BST）的最大深度
我知道使用queue [level order traversal]的方法，但時間複雜度是O（N），因爲我們需要訪問整個樹。 但它不使用樹是BST還是二叉樹的信息。
算法對於BST是否保持不變？或者可以使用給定樹是BST的事實來改進算法嗎？
A
回答
1
我不認爲樹是BST或不改變任何東西的事實，你仍然不得不在最壞的情況下訪問所有節點，這使得它成爲O（N）。我想在最好的情況下，你只需要做O（log（N）），但這是最好的情況，你只需沿着樹的深度走，並且不會訪問其他節點。
相關問題
- 1. 尋找樹的最大深度
- 2. 查找二叉樹的最大深度
- 3. 最大的子樹哪個是二叉搜索樹（BST）
- 4. 查找二叉搜索樹的最小深度
- 5. 二叉樹到二叉搜索樹（BST）
- 6. 二叉搜索樹bst
- 7. 二叉搜索樹（BST）
- 8. 在二叉搜索樹中打印最大深度
- 9. 計算二叉搜索樹的深度？
- 10. 二叉搜索樹 - 查找高度和深度
- 11. 查找二叉樹中節點的深度不是BST
- 12. 在二叉搜索樹中查找K個最大的元素
- 13. Java：二叉搜索的最小深度樹遞歸
- 14. 在二進制搜索樹中查找數據點的深度
- 15. 查找樹的最大深度
- 16. 功能找到最深的二叉搜索樹總和
- 17. 非遞歸BST（二叉搜索樹）
- 18. 二叉樹中最大的二叉樹搜索樹
- 19. 最大樹深度在Haskell
- 20. 二叉搜索樹最大值
- 21. 深度優先搜索中的Python「RuntimeError：最大遞歸深度」
- 22. 大小爲1的二叉樹的最大深度
- 23. 二叉樹的最小深度
- 24. 查找二叉搜索樹的最小元素
- 25. 二叉查找樹的深度
- 26. 查找二叉樹的深度
- 27. 查找二叉樹的最深節點
- 28. 計算在二進制搜索樹中查找最大值的路徑長度
- 29. 如何查找並返回二叉樹的最底部（最深節點）節點？二叉搜索樹？
- 30. 查找二叉搜索樹
什麼意思是「在最好的情況下，你只需要做O（log（N））」？這是否意味着樹是自我平衡的？ –
是的，當你不得不在任何層次上訪問從左到右的任何節點時，你會有O（log（N））。 –