java - 从给定的前序遍历构造 BST？

Question

本题来自http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/

我可以想到下面的简单算法(类似于 Java 内部对 TreeMap 遵循的算法)

1. 我们可以开始一个一个地添加节点。添加时开始将每个节点与根节点进行比较，然后决定右/左位置
2. 递归地做

但我没有在谷歌或同一链接的任何地方看到它的提及。根据我的理解，它的时间复杂度将是 nlog(n)。我理解它并不比 O(n) 的第二种方法好，但比 O(n^2) 的第一种方法好，不是吗？

Answer 1

你是正确的，它比第一种方法更好，但第二种方法甚至更好，因为时间复杂度为 O(n)。

当您没有提前完成输入时，您建议的方法会更好，但是当您准备好完整输入时，您不必一一添加，这涉及查找每个节点的位置 (logn)。所以对于 n 个节点，它将是 nlog(n)