为了账号安全,请及时绑定邮箱和手机立即绑定

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

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

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

3 回答

?
慕码人8056858

TA贡献1803条经验 获得超6个赞

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

}


查看完整回答
反对 回复 2019-10-14
?
江户川乱折腾

TA贡献1851条经验 获得超5个赞

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


查看完整回答
反对 回复 2019-10-14
  • 3 回答
  • 0 关注
  • 610 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信