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

Question

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

Answer 1

一个更简单的解决方案是进行有序遍历并跟踪当前要打印的元素（不打印）。当我们达到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); 

}

Answer 2

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