从给定的前序遍历构造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？

回答

相关问题