0
  • 聊天消息
  • 系統(tǒng)消息
  • 評論與回復(fù)
登錄后你可以
  • 下載海量資料
  • 學(xué)習(xí)在線課程
  • 觀看技術(shù)視頻
  • 寫文章/發(fā)帖/加入社區(qū)
會員中心
电子发烧友
开通电子发烧友VIP会员 尊享10大特权
海量资料免费下载
精品直播免费看
优质内容免费畅学
课程9折专享价
創(chuàng)作中心

完善資料讓更多小伙伴認(rèn)識你,還能領(lǐng)取20積分哦,立即完善>

3天內(nèi)不再提示

如何修剪二叉搜索樹

算法與數(shù)據(jù)結(jié)構(gòu) ? 來源:代碼隨想錄 ? 作者:程序員Carl ? 2021-10-11 14:16 ? 次閱讀
加入交流群
微信小助手二維碼

掃碼添加小助手

加入工程師交流群

如果不對遞歸有深刻的理解,本題有點難。單純移除一個節(jié)點那還不夠,要修剪!

669. 修剪二叉搜索樹

給定一個二叉搜索樹,同時給定最小邊界L 和最大邊界 R。通過修剪二叉搜索樹,使得所有節(jié)點的值在[L, R]中 (R>=L) 。你可能需要改變樹的根節(jié)點,所以結(jié)果應(yīng)當(dāng)返回修剪好的二叉搜索樹的新的根節(jié)點。

思路

相信看到這道題目大家都感覺是一道簡單題(事實上leetcode上也標(biāo)明是簡單)。

但還真的不簡單!

遞歸法

直接想法就是:遞歸處理,然后遇到root->val < low || root->val > high的時候直接return NULL,一波修改,趕緊利落。

不難寫出如下代碼:

classSolution{
public:
TreeNode*trimBST(TreeNode*root,intlow,inthigh){
if(root==nullptr||root->valval>high)returnnullptr;
root->left=trimBST(root->left,low,high);
root->right=trimBST(root->right,low,high);
returnroot;
}
};

然而[1, 3]區(qū)間在二叉搜索樹的中可不是單純的節(jié)點3和左孩子節(jié)點0就決定的,還要考慮節(jié)點0的右子樹

所以以上的代碼是不可行的!

從圖中可以看出需要重構(gòu)二叉樹,想想是不是本題就有點復(fù)雜了。

其實不用重構(gòu)那么復(fù)雜。

在上圖中我們發(fā)現(xiàn)節(jié)點0并不符合區(qū)間要求,那么將節(jié)點0的右孩子 節(jié)點2 直接賦給 節(jié)點3的左孩子就可以了(就是把節(jié)點0從二叉樹中移除)

理解了最關(guān)鍵部分了我們在遞歸三部曲:

  • 確定遞歸函數(shù)的參數(shù)以及返回值

這里我們?yōu)槭裁葱枰祷刂的兀?/p>

因為是要遍歷整棵樹,做修改,其實不需要返回值也可以,我們也可以完成修剪(其實就是從二叉樹中移除節(jié)點)的操作。

但是有返回值,更方便,可以通過遞歸函數(shù)的返回值來移除節(jié)點。

這樣的做法在二叉樹:搜索樹中的插入操作二叉樹:搜索樹中的刪除操作中大家已經(jīng)了解過了。

代碼如下:

TreeNode*trimBST(TreeNode*root,intlow,inthigh)
  • 確定終止條件

修剪的操作并不是在終止條件上進(jìn)行的,所以就是遇到空節(jié)點返回就可以了。

if(root==nullptr)returnnullptr;
  • 確定單層遞歸的邏輯

如果root(當(dāng)前節(jié)點)的元素小于low的數(shù)值,那么應(yīng)該遞歸右子樹,并返回右子樹符合條件的頭結(jié)點。

代碼如下:

if(root->valright,low,high);//尋找符合區(qū)間[low,high]的節(jié)點
returnright;
}

如果root(當(dāng)前節(jié)點)的元素大于high的,那么應(yīng)該遞歸左子樹,并返回左子樹符合條件的頭結(jié)點。

代碼如下:

if(root->val>high){
TreeNode*left=trimBST(root->left,low,high);//尋找符合區(qū)間[low,high]的節(jié)點
returnleft;
}

接下來要將下一層處理完左子樹的結(jié)果賦給root->left,處理完右子樹的結(jié)果賦給root->right。

最后返回root節(jié)點,代碼如下:

root->left=trimBST(root->left,low,high);//root->left接入符合條件的左孩子
root->right=trimBST(root->right,low,high);//root->right接入符合條件的右孩子
returnroot;

此時大家是不是還沒發(fā)現(xiàn)這多余的節(jié)點究竟是如何從二叉樹中移除的呢?

在回顧一下上面的代碼,針對下圖中二叉樹的情況:

如下代碼相當(dāng)于把節(jié)點0的右孩子(節(jié)點2)返回給上一層,

if(root->valright,low,high);//尋找符合區(qū)間[low,high]的節(jié)點
returnright;
}

然后如下代碼相當(dāng)于用節(jié)點3的左孩子 把下一層返回的 節(jié)點0的右孩子(節(jié)點2) 接住。

root->left=trimBST(root->left,low,high);

此時節(jié)點3的右孩子就變成了節(jié)點2,將節(jié)點0從二叉樹中移除了。

最后整體代碼如下:

classSolution{
public:
TreeNode*trimBST(TreeNode*root,intlow,inthigh){
if(root==nullptr)returnnullptr;
if(root->valright,low,high);//尋找符合區(qū)間[low,high]的節(jié)點
returnright;
}
if(root->val>high){
TreeNode*left=trimBST(root->left,low,high);//尋找符合區(qū)間[low,high]的節(jié)點
returnleft;
}
root->left=trimBST(root->left,low,high);//root->left接入符合條件的左孩子
root->right=trimBST(root->right,low,high);//root->right接入符合條件的右孩子
returnroot;
}
};

精簡之后代碼如下:

classSolution{
public:
TreeNode*trimBST(TreeNode*root,intlow,inthigh){
if(root==nullptr)returnnullptr;
if(root->valreturntrimBST(root->right,low,high);
if(root->val>high)returntrimBST(root->left,low,high);
root->left=trimBST(root->left,low,high);
root->right=trimBST(root->right,low,high);
returnroot;
}
};

只看代碼,其實不太好理解節(jié)點是符合移除的,這一塊大家可以自己在模擬模擬!

迭代法

因為二叉搜索樹的有序性,不需要使用棧模擬遞歸的過程。

在剪枝的時候,可以分為三步:

  • 將root移動到[L, R] 范圍內(nèi),注意是左閉右閉區(qū)間
  • 剪枝左子樹
  • 剪枝右子樹

代碼如下:

classSolution{
public:
TreeNode*trimBST(TreeNode*root,intL,intR){
if(!root)returnnullptr;

//處理頭結(jié)點,讓root移動到[L,R]范圍內(nèi),注意是左閉右閉
while(root!=nullptr&&(root->valval>R)){
if(root->valright;//小于L往右走
elseroot=root->left;//大于R往左走
}
TreeNode*cur=root;
//此時root已經(jīng)在[L,R]范圍內(nèi),處理左孩子元素小于L的情況
while(cur!=nullptr){
while(cur->left&&cur->left->valleft=cur->left->right;
}
cur=cur->left;
}
cur=root;

//此時root已經(jīng)在[L,R]范圍內(nèi),處理右孩子大于R的情況
while(cur!=nullptr){
while(cur->right&&cur->right->val>R){
cur->right=cur->right->left;
}
cur=cur->right;
}
returnroot;
}
};

總結(jié)

修剪二叉搜索樹其實并不難,但在遞歸法中大家可看出我費了很大的功夫來講解如何刪除節(jié)點的,這個思路其實是比較繞的。

最終的代碼倒是很簡潔。

如果不對遞歸有深刻的理解,這道題目還是有難度的!

本題我依然給出遞歸法和迭代法,初學(xué)者掌握遞歸就可以了,如果想進(jìn)一步學(xué)習(xí),就把迭代法也寫一寫。

其他語言版本

Java

classSolution{
publicTreeNodetrimBST(TreeNoderoot,intlow,inthigh){
if(root==null){
returnnull;
}
if(root.valreturntrimBST(root.right,low,high);
}
if(root.val>high){
returntrimBST(root.left,low,high);
}
//root在[low,high]范圍內(nèi)
root.left=trimBST(root.left,low,high);
root.right=trimBST(root.right,low,high);
returnroot;
}
}

Python

classSolution:
deftrimBST(self,root:TreeNode,low:int,high:int)->TreeNode:
ifnotroot:returnroot
ifroot.valreturnself.trimBST(root.right,low,high)//尋找符合區(qū)間[low,high]的節(jié)點
ifroot.val>high:
returnself.trimBST(root.left,low,high)//尋找符合區(qū)間[low,high]的節(jié)點
root.left=self.trimBST(root.left,low,high)//root->left接入符合條件的左孩子
root.right=self.trimBST(root.right,low,high)//root->right接入符合條件的右孩子
returnroot
責(zé)任編輯:haq

聲明:本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點僅代表作者本人,不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學(xué)習(xí)之用,如有內(nèi)容侵權(quán)或者其他違規(guī)問題,請聯(lián)系本站處理。 舉報投訴
  • 源代碼
    +關(guān)注

    關(guān)注

    96

    文章

    2953

    瀏覽量

    68190
  • 二叉樹
    +關(guān)注

    關(guān)注

    0

    文章

    74

    瀏覽量

    12604

原文標(biāo)題:修剪一棵二叉搜索樹

文章出處:【微信號:TheAlgorithm,微信公眾號:算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。

收藏 0人收藏
加入交流群
微信小助手二維碼

掃碼添加小助手

加入工程師交流群

    評論

    相關(guān)推薦
    熱點推薦

    神經(jīng)網(wǎng)絡(luò)壓縮框架 (NNCF) 中的過濾器修剪統(tǒng)計數(shù)據(jù)怎么查看?

    無法觀察神經(jīng)網(wǎng)絡(luò)壓縮框架 (NNCF) 中的過濾器修剪統(tǒng)計數(shù)據(jù)
    發(fā)表于 03-06 07:10

    求解答,設(shè)備問題

    請問,rk3588j要再提取一個USB3.0接口設(shè)備怎么改
    發(fā)表于 02-20 11:22

    百度搜索全量上線DeepSeek滿血版,開啟AI搜索新體驗

    近日,百度搜索迎來了重大更新,全量上線了DeepSeek滿血版。這一更新意味著用戶現(xiàn)在可以在百度App中體驗到更加智能、高效的搜索服務(wù)。 用戶只需在百度App中輸入任意搜索詞,完成一輪搜索
    的頭像 發(fā)表于 02-18 15:15 ?1174次閱讀

    百度搜索與文心智能體平臺接入DeepSeek及文心大模型深度搜索

    近日,百度搜索與文心智能體平臺聯(lián)合宣布了一項重要更新:將全面接入DeepSeek及文心大模型最新的深度搜索功能。這一更新將為用戶和開發(fā)者帶來更加智能、高效的搜索和智能體創(chuàng)建體驗。 據(jù)悉,搜索
    的頭像 發(fā)表于 02-17 09:14 ?600次閱讀

    Kaggle知識點:7種超參數(shù)搜索方法

    數(shù)據(jù)科學(xué)超參數(shù)搜索確實是機(jī)器學(xué)習(xí)生命周期中不可或缺的一步,特別是在模型性能方面。正確的超參數(shù)選擇可以顯著提高模型的準(zhǔn)確性、對未見數(shù)據(jù)的泛化能力以及收斂速度。不當(dāng)?shù)某瑓?shù)選擇可能導(dǎo)致過擬合或欠擬合等
    的頭像 發(fā)表于 02-08 14:28 ?908次閱讀
    Kaggle知識點:7種超參數(shù)<b class='flag-5'>搜索</b>方法

    OpenAI免費開放ChatGPT搜索功能

    近日,OpenAI宣布了一項重大決策:向所有用戶免費開放ChatGPT搜索功能。這一舉措無疑將為用戶帶來更加高效、智能的搜索體驗。 與谷歌等傳統(tǒng)搜索引擎的收錄模式相比,ChatGPT搜索
    的頭像 發(fā)表于 02-06 14:35 ?476次閱讀

    嵌入式學(xué)習(xí)-飛凌嵌入式ElfBoard ELF 1板卡-初識設(shè)備之設(shè)備組成和結(jié)構(gòu)

    的name和value。在設(shè)備中,可描述的信息包括:一、CPU的數(shù)量和類別;、內(nèi)存基地址和大??;三、總線和橋;四、外設(shè)連接;五、中斷控制器和中斷使用情況;六、GPIO控制器和GPIO使用情況;七
    發(fā)表于 01-08 08:32

    飛凌嵌入式ElfBoard ELF 1板卡-初識設(shè)備之設(shè)備組成和結(jié)構(gòu)

    的name和value。在設(shè)備中,可描述的信息包括:一、CPU的數(shù)量和類別;、內(nèi)存基地址和大?。蝗?、總線和橋;四、外設(shè)連接;五、中斷控制器和中斷使用情況;六、GPIO控制器和GPIO使用情況;七
    發(fā)表于 01-07 09:16

    OpenAI推出ChatGPT搜索功能

    近日,OpenAI再次邁出了重要的一步,為其廣受好評的ChatGPT平臺添加了一項全新的搜索功能。 據(jù)悉,這項被命名為“ChatGPT搜索”的新功能,將為用戶帶來前所未有的搜索體驗。以往,當(dāng)用戶需要
    的頭像 發(fā)表于 11-04 10:34 ?659次閱讀

    OpenAI在ChatGPT增添搜索功能

    近日,OpenAI宣布為其旗艦產(chǎn)品ChatGPT增添全新的搜索功能,此舉標(biāo)志著該公司對Alphabet旗下谷歌的直接挑戰(zhàn)進(jìn)一步升級。OpenAI周四正式揭曉了這一名為“ChatGPT搜索”的新功能
    的頭像 發(fā)表于 11-01 17:01 ?732次閱讀

    谷歌取消“站點鏈接搜索框”,適應(yīng)新搜索需求

    近日,谷歌發(fā)布了一則通知,決定取消搜索結(jié)果中的“站點鏈接搜索框”。這一功能已經(jīng)陪伴了用戶十多年,它允許用戶在特定網(wǎng)站上進(jìn)行更深入的搜索,為許多網(wǎng)民提供了便利。然而,隨著時代的變遷和技術(shù)的進(jìn)步,這一
    的頭像 發(fā)表于 10-23 11:20 ?656次閱讀

    什么是默克爾(Merkle Tree)?如何計算默克爾根?

    01 默克爾的概念 默克爾(Merkle Tree)是一種特殊的二叉樹,它的每個節(jié)點都存儲了一個數(shù)據(jù)塊的哈希值。哈希值是一種可以將任意長度的數(shù)據(jù)轉(zhuǎn)換為固定長度的字符串的算法,它具有唯一性和不可
    的頭像 發(fā)表于 09-30 18:22 ?2203次閱讀
    什么是默克爾<b class='flag-5'>樹</b>(Merkle Tree)?如何計算默克爾根?

    月訪問量超2億,增速113%!360AI搜索成為全球增速最快的AI搜索引擎

    和系統(tǒng)自動匹配最佳模型,這使得360AI搜索獲得了獨一無的技術(shù)優(yōu)勢。除了通用大模型,360AI搜索還配備了眾多搜索場景專用模型,精準(zhǔn)提升特定場景下的
    的頭像 發(fā)表于 09-09 13:44 ?852次閱讀
    月訪問量超2億,增速113%!360AI<b class='flag-5'>搜索</b>成為全球增速最快的AI<b class='flag-5'>搜索</b>引擎

    AI搜索新貴彎道超車難

    新玩家高調(diào)入場,老玩家默默升級,搜索市場進(jìn)入新一輪洗牌階段。最近一段時間,老舊的搜索行業(yè)開出了新花。從2009年開始,谷歌、百度成了搜索領(lǐng)域繞不開的存在,它們占據(jù)了全球搜索引擎市場絕大
    的頭像 發(fā)表于 07-09 08:05 ?231次閱讀
    AI<b class='flag-5'>搜索</b>新貴彎道超車難

    指電極上覆蓋敏感材料的阻值計算

    覆蓋的敏感材料厚度超出指厚度時計算電阻,是否可以視作指電極指間電阻多個周期串聯(lián)后與超出指厚度部分敏感材料電阻并聯(lián)
    發(fā)表于 07-05 14:48

    電子發(fā)燒友

    中國電子工程師最喜歡的網(wǎng)站

    • 2931785位工程師會員交流學(xué)習(xí)
    • 獲取您個性化的科技前沿技術(shù)信息
    • 參加活動獲取豐厚的禮品