用最优方法求二分查找树的第k个最小元素
用最优方法求二分查找树的第k个最小元素
提问于 2010-02-25 04:18:05
我需要在二进制搜索树中找到第k个最小的元素，而不使用任何静态/全局变量。如何有效地实现它？我脑海中的解决方案是在O(n)中进行操作，这是最坏的情况，因为我计划对整个树进行顺序遍历。但在内心深处，我觉得我并没有在这里使用BST属性。我的假设解决方案是否正确，或者是否有更好的解决方案？
回答 28
Stack Overflow用户
发布于 2010-12-01 12:14:44
一种更简单的解决方案是按顺序遍历并跟踪当前要打印的元素(不打印它)。当我们到达k时，打印元素并跳过树遍历的其余部分。
void findK(Node* p, int* k) {
if(!p || k < 0) return;
findK(p->left, k);
--k;
if(k == 0) {
print p->data;
return;
}
findK(p->right, k);
}Stack Overflow用户
发布于 2010-06-10 06:01:38
public int ReturnKthSmallestElement1(int k)
{
Node node = Root;
int count = k;
int sizeOfLeftSubtree = 0;
while(node != null)
{
sizeOfLeftSubtree = node.SizeOfLeftSubtree();
if (sizeOfLeftSubtree + 1 == count)
return node.Value;
else if (sizeOfLeftSubtree < count)
{
node = node.Right;
count -= sizeOfLeftSubtree+1;
}
else
{
node = node.Left;
}
}
return -1;
}这是我基于上面的算法用C#实现的，我只是想把它贴出来，这样人们就可以更好地理解它对我的作用
谢谢你，IVlad
Stack Overflow用户
发布于 2012-12-29 12:09:50
//添加不带递归的java版本
public static <T> void find(TreeNode<T> node, int num){
Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
TreeNode<T> current = node;
int tmp = num;
while(stack.size() > 0 || current!=null){
if(current!= null){
stack.add(current);
current = current.getLeft();
}else{
current = stack.pop();
tmp--;
if(tmp == 0){
System.out.println(current.getValue());
return;
}
current = current.getRight();
}
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2329171
复制相关文章
相似问题