use*_*342 0 algorithm binary-search-tree preorder
当被要求创建一个给定前序遍历的BST时,会给出如下答案:http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/
这需要很多代码.
我的问题是,为什么我不能插入空树给我正确的答案？有没有简单插入可能导致错误答案的例子？例如,在该链接中给出的示例中,我们将{10,5,1,7,40,50}作为前序遍历.但是,不只是按预定顺序列表的顺序使用常规BST插入方法6次给出适当的树？我可以得到一个反例和/或解释为什么我不正确吗？我一直无法想出一个反例.
只调用insert正确的次数应该确实产生正确的树 - 但它需要O(n log n)复杂度,其中可以用O(N)复杂度完成.
老实说,除非你处理大量数据,否则对你来说差异可能并不十分重要.