從給定的前序遍歷構造BST？

來自這個問題http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/從給定的前序遍歷構造BST？

我能想到下面簡單的算法（一種相同的是java的內部遵循TreeMap中）

我們可以開始添加節點一個接一個的。同時加入開始比較根節點的每個節點，然後再決定左/右位置
就做遞歸

但我沒有看到任何地方對谷歌或同一link.Per我的理解中它的它提到的時間複雜度會是nlog（n）。我理解它不比第二種方法更好，即O（n），但比第一種O（n^2）好。是不是？

2016-10-11 user3198603

這個https://stackoverflow.com/questions/19640382/bst-from-preorder-by-just-inserting-the-nodes-in-same-order討論你提到的方法相同。正如在答覆中所述，這將採取nolg（n）。 – LearningC

你是正確的，它比第一種方法更好，但第二種方法更好，因爲時間複雜度是O（n）。

當您沒有提前完成輸入時，您建議的方法會更好，但是當您準備好完整的輸入時，則不必逐個添加它，其中包括查找每個節點（logn）的位置。所以對於n個節點，它將是nlog（n）

來源

2016-10-11 15:17:15

從給定的前序遍歷構造BST？

回答

相關問題