以最佳方式在二进制搜索树中找到第k个最小元素

Question

我需要在二进制搜索树中找到第k个最小的元素，而无需使用任何静态/全局变量。如何有效实现？我想到的解决方案是在O（n）中进行操作，这是最糟糕的情况，因为我计划对整个树进行有序遍历。但在内心深处，我觉得我没有在这里使用BST属性。我的假设解决方案正确还是有更好的解决方案？

Answer 1

一个更简单的解决方案是进行有序遍历并跟踪当前要打印的元素（不打印）。当我们达到k时，打印元素并跳过其余的树遍历。void findK(Node* p, int* k) {&nbsp; if(!p || k < 0) return;&nbsp; findK(p->left, k);&nbsp; --k;&nbsp; if(k == 0) {&nbsp;&nbsp; &nbsp; print p->data;&nbsp; &nbsp; return;&nbsp;&nbsp;&nbsp; }&nbsp;&nbsp; findK(p->right, k);&nbsp;}

Answer 2

public int ReturnKthSmallestElement1(int k)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; Node node = Root;&nbsp; &nbsp; &nbsp; &nbsp; int count = k;&nbsp; &nbsp; &nbsp; &nbsp; int sizeOfLeftSubtree = 0;&nbsp; &nbsp; &nbsp; &nbsp; while(node != null)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sizeOfLeftSubtree = node.SizeOfLeftSubtree();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (sizeOfLeftSubtree + 1 == count)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return node.Value;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else if (sizeOfLeftSubtree < count)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node = node.Right;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count -= sizeOfLeftSubtree+1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node = node.Left;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return -1;&nbsp; &nbsp; }这是我基于上述算法在C＃中的实现，只是以为我会发布它，以便人们可以更好地理解它对我有用谢谢你IVlad