第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號(hào)安全，請(qǐng)及時(shí)綁定郵箱和手機(jī)立即綁定
已解決430363個(gè)問(wèn)題，去搜搜看，總會(huì)有你想問(wèn)的

以最佳方式在二進(jìn)制搜索樹(shù)中找到第k個(gè)最小元素

以最佳方式在二進(jìn)制搜索樹(shù)中找到第k個(gè)最小元素

我需要在二進(jìn)制搜索樹(shù)中找到第k個(gè)最小的元素，而無(wú)需使用任何靜態(tài)/全局變量。如何有效實(shí)現(xiàn)？我想到的解決方案是在O（n）中進(jìn)行操作，這是最糟糕的情況，因?yàn)槲矣?jì)劃對(duì)整個(gè)樹(shù)進(jìn)行有序遍歷。但在內(nèi)心深處，我覺(jué)得我沒(méi)有在這里使用BST屬性。我的假設(shè)解決方案正確還是有更好的解決方案？
查看完整描述

3 回答

?
慕碼人8056858

TA貢獻(xiàn)1803條經(jīng)驗(yàn) 獲得超6個(gè)贊

一個(gè)更簡(jiǎn)單的解決方案是進(jìn)行有序遍歷并跟蹤當(dāng)前要打印的元素（不打?。?。當(dāng)我們達(dá)到k時(shí)，打印元素并跳過(guò)其余的樹(shù)遍歷。


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); 

}


查看完整回答
反對(duì) 回復(fù) 2019-10-14
?
江戶川亂折騰

TA貢獻(xiàn)1851條經(jīng)驗(yàn) 獲得超5個(gè)贊

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＃中的實(shí)現(xiàn)，只是以為我會(huì)發(fā)布它，以便人們可以更好地理解它對(duì)我有用


謝謝你IVlad


查看完整回答
反對(duì) 回復(fù) 2019-10-14
  • 3 回答
  • 0 關(guān)注
  • 698 瀏覽
慕課專欄
更多

添加回答

舉報(bào)

0/150
提交
取消
微信客服

購(gòu)課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

 幫助反饋 APP下載

慕課網(wǎng)APP
您的移動(dòng)學(xué)習(xí)伙伴

 公眾號(hào)

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號(hào)