二叉搜索樹刪除節(jié)點 動畫演示

Day60：刪除二叉搜索樹的某個節(jié)點

1 題目

給定一個二叉搜索樹的根節(jié)點 root 和一個值 key，刪除二叉搜索樹中的 key 對應的節(jié)點，并保證二叉搜索樹的性質(zhì)不變。返回二叉搜索樹（有可能被更新）的根節(jié)點的引用。

一般來說，刪除節(jié)點可分為兩個步驟：

• 首先找到需要刪除的節(jié)點；
• 如果找到了，刪除它。

說明：要求算法時間復雜度為 O(h)，h 為樹的高度。

示例:

root = [5,3,6,2,4,null,7]

key = 3

????5
???/?\
??3???6
?/?\???\
2???4???7

給定需要刪除的節(jié)點值是 3，所以我們首先找到 3 這個節(jié)點，然后刪除它。

一個正確的答案是 [5,4,6,2,null,null,7], 如下圖所示。

????5
???/?\
??4???6
?/?????\
2???????7

另一個正確答案是 [5,2,6,null,4,null,7]。

????5
???/?\
??2???6
???\???\
????4???7

2 分析過程

這道題被leetcode定為中等難度級別，實話講確實屬于這類級別，雖然思路不難，但是要想一次寫出準確無誤的代碼，仍然不是一件簡單的事情。如果你第一次做這道題能很快寫出來，說明你對遞歸的理解、指針的掌控都達到了一定水平。

這道題的思路很straitforward，根據(jù)BST的性質(zhì)，具體說來分為如下幾種情況：

1. 如果被刪除節(jié)點關鍵碼key小于當前根節(jié)點nodei.val，則問題規(guī)模直接降階到左子樹中

2. 關鍵碼key大于當前根節(jié)點nodei.val，直接到右子樹中查找

3. key等于當前根節(jié)點nodei.val，又分為4種情況：

   (1). nodei 無左右子樹，摘除nodei節(jié)點，等于直接返回 None

   (2). nodei 僅有左子樹，摘除nodei節(jié)點，等于直接返回 nodei.left

   (3). nodei 僅有右子樹，摘除nodei節(jié)點，等于直接返回 nodei.right

   (4). nodei 都有左右子樹，麻煩一點，方法之一：選擇以nodei.right為根節(jié)點的樹中最左側(cè)節(jié)點，然后替換nodei

最后返回 nodei.

你看，上面的思路應該足夠清晰，但是兌現(xiàn)為代碼絕對又是另一回事。你首先要對遞歸有深刻的理解，其次像鏈表、二叉樹等這類具備遞歸的數(shù)據(jù)結(jié)構(gòu)，操作它們節(jié)點引用問題要時刻保持清醒，很容易出錯。

3 如何寫出代碼

老規(guī)矩，這是我們的節(jié)點定義：

#?Definition?for?a?binary?tree?node.
#?class?TreeNode(object):
#?????def?__init__(self,?x):
#?????????self.val?=?x
#?????????self.left?=?None
#?????????self.right?=?None

解決方案對象的主方法，調(diào)用自定義方法self.__delNodei(root,key)，這個方法的構(gòu)思思路是這樣：

第一個參數(shù)是BST樹中的任意節(jié)點，因為BST嚴格滿足遞歸，所以選取任意一個以節(jié)點nodei為根的樹，刪除里面等于key的節(jié)點。因此，這個功能一旦實現(xiàn)后，只需在參數(shù)賦值時賦值它為root即可。

class?Solution(object):
????def?deleteNode(self,?root,?key):
????????"""
????????:type?root:?TreeNode
????????:type?key:?int
????????:rtype:?TreeNode
????????"""
????????return?self.__delNodei(root,key)

所以關鍵是如何寫出def __delNodei(self,nodei,key)方法，下面我們一步一步分析。

根據(jù)上面的4種情況分析，我們在情況4時會用到找樹的最左節(jié)點，為此先寫出這個方法def __findMinNode(self,nodei)：

????#?找到以nodei為根節(jié)點樹的最小值
????def?__findMinNode(self,nodei):
????????if?not?nodei.left:
????????????return?nodei
????????while?nodei.left:
????????????nodei?=?nodei.left
????????return?nodei

這個比較簡單，是鏈表、二叉樹等遞歸結(jié)構(gòu)的常規(guī)迭代思路，注意與向量表i=i+1迭代思路的區(qū)別。

先寫出第一種大情況，比較簡單。因為方法self.__delNodei(nodei.left,key)實現(xiàn)刪除等于key的節(jié)點后返回對nodei.left節(jié)點的引用，所以將nodei的left域指向它即可。

????#?假定已經(jīng)查詢到nodei節(jié)點，刪除后返回nodei節(jié)點的引用
????def?__delNodei(self,nodei,key):
????????if?not?nodei:
????????????return?None

????????#若滿足下面條件，一定在左子樹
????????if?key?????????????nodei.left?=?self.__delNodei(nodei.left,key)?#?刪除后返回nodei.left節(jié)點的引用???

以下面二叉搜索樹刪除值等于3的節(jié)點為例演示，伸入到左子樹：

再寫出第二種大情況，與上類似：

#?一定在右子樹
????????elif?nodei.val?????????????nodei.right?=?self.__delNodei(nodei.right,key)#?刪除后返回nodei.right節(jié)點的引用

再寫出第三種大情況，即找到了等于key節(jié)點，又分四種小情況：

被刪除節(jié)點是葉子節(jié)點：直接返回None，就是摘除它了：

?#?nodei.val==?key，刪除nodei
????????else:
????????????#?情況1：被刪除節(jié)點是葉子節(jié)點
????????????if?not?nodei.left?and?not?nodei.right:
????????????????return?None??#?置為None

第二、三種小情況很相似，跳過被刪除節(jié)點nodei，直接返回nodei.left 或 node.right 即可：

????????????#?情況2：被刪除節(jié)點無右子樹
????????????if?not?nodei.right:
????????????????return?nodei.left?#?跳過nodei,返回指向nodei.left，相當于刪除了nodei
????????????#?情況3：被刪除節(jié)點無左子樹
????????????if?not?nodei.left:
????????????????return?nodei.right

最后一種小情況，大家直接看注釋吧：

????????????#?情況4：被刪除節(jié)點左右子樹都不為空
????????????#?先找到右子樹中最左節(jié)點，即右子樹最小值節(jié)點
????????????minNodei?=?self.__findMinNode(nodei.right)
????????????nodei.val?=?minNodei.val
????????????#?刪除minNodei，同時返回nodei.right的引用，并賦值給nodei.right
????????????##?切記：key已經(jīng)不是__delNodei的參數(shù)key，而是我們找到的minNodei的val值
????????????nodei.right?=?self.__delNodei(nodei.right,minNodei.val)?
????????
????????return?nodei