algorithm - 我关于先序遍历的想法有什么问题

Question

当要求根据前序遍历创建 BST 时，给出的答案如下:http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/

需要大量代码。

我的问题是，为什么我不能只插入一个空树来给我正确答案？有没有简单插入会导致错误答案的例子？例如，在该链接中给出的示例中，我们将 {10, 5, 1, 7, 40, 50} 作为前序遍历。但是，仅仅按照预序列表的顺序使用常规 BST 插入方法 6 次不就可以给出合适的树吗？我可以得到一个反例和/或解释为什么我不正确吗？我一直想不出反例。

Answer 1

只需调用 insert 正确的次数确实应该生成正确的树——但它需要 O(n log n) 的复杂度，可以复杂度为 O(N)。

老实说，除非您处理的是大量数据，否则差异对您来说可能不会非常重要。