刪除二叉搜索樹中的節(jié)點(diǎn)

今天分享的題目來源于 LeetCode 第 450 號(hào)問題：刪除二叉搜索樹中的節(jié)點(diǎn)。雖然它的難度是中等，但實(shí)際上很好理解，請(qǐng)往下看！

題目描述

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

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

首先找到需要?jiǎng)h除的節(jié)點(diǎn)；

如果找到了，刪除它。

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

示例:

root=[5,3,6,2,4,null,7] key=3 5 / 36 / 247 給定需要?jiǎng)h除的節(jié)點(diǎn)值是3，所以我們首先找到3這個(gè)節(jié)點(diǎn)，然后刪除它。 一個(gè)正確的答案是[5,4,6,2,null,null,7], 如下圖所示。 5 / 46 / 27 另一個(gè)正確答案是[5,2,6,null,4,null,7]。 5 / 26 47

題目解析

在二叉搜索樹上刪除一個(gè)節(jié)點(diǎn)，這道題目有一個(gè)隱含的條件，就是樹上節(jié)點(diǎn)的值不重復(fù)。

另外題目還要求時(shí)間復(fù)雜度需要保證 O(h) 這里的 h 表示的是二叉樹的高度。

其實(shí)這個(gè)題目是分成兩個(gè)步驟的，第一個(gè)是找到對(duì)應(yīng)的節(jié)點(diǎn)，第二個(gè)是刪除節(jié)點(diǎn)。

因?yàn)槭嵌嫠阉鳂洌瑢?duì)于樹上每個(gè)節(jié)點(diǎn)來說，其右子樹的節(jié)點(diǎn)都要大于其左子樹的節(jié)點(diǎn)，那么要找對(duì)應(yīng)節(jié)點(diǎn)，我們可以從根節(jié)點(diǎn)開始，一路比較，大的話就去右邊找，小的話就去左邊找，這樣每次我們都往下，可以保證時(shí)間復(fù)雜度是 O(h)。

當(dāng)我們找到了要?jiǎng)h除的節(jié)點(diǎn)，在刪除這一步就會(huì)有很多的細(xì)節(jié)，主要是因?yàn)槲覀冃枰{(diào)整余下的結(jié)構(gòu)，以維持二叉搜索樹的性質(zhì)。

針對(duì)這個(gè)問題，我們可以分情況討論：

5 / 36 / 247 / 18

情況 1：當(dāng)刪除的節(jié)點(diǎn)沒有左右子樹，比如上圖的 4、8、1
這時(shí)直接刪除即可，樹依舊可以保持二叉搜索樹的性質(zhì)

情況 2：當(dāng)刪除的節(jié)點(diǎn)有左子樹沒有右子樹，比如上圖的 2
這時(shí)我們只需要將整個(gè)左子樹移到當(dāng)前位置即可
也就是將左子樹的根節(jié)點(diǎn)放到刪除節(jié)點(diǎn)的位置，其余不變

情況 3：當(dāng)刪除的節(jié)點(diǎn)沒有左子樹有右子樹，比如上圖的 6、7
這時(shí)我們只需要將整個(gè)右子樹移到當(dāng)前位置即可
也就是將右子樹的根節(jié)點(diǎn)放到刪除節(jié)點(diǎn)的位置，其余不變

情況 4：當(dāng)刪除的節(jié)點(diǎn)既有左子樹又有右子樹，比如上圖的 5、3
這時(shí)就有兩種方法供選擇：
去到左子樹中，找到值最大節(jié)點(diǎn)，將右子樹全部移到這個(gè)節(jié)點(diǎn)下
去到右子樹中，找到值最小節(jié)點(diǎn)，將左子樹全部移到這個(gè)節(jié)點(diǎn)下

通過上面的討論分析，我們有了大致的思路。在實(shí)現(xiàn)方面，我們可以借助遞歸來巧妙地達(dá)到刪除對(duì)應(yīng)節(jié)點(diǎn)的目的。

圖片描述

參考代碼

//五分鐘學(xué)算法 publicTreeNodedeleteNode(TreeNoderoot,intkey){ if(root==null){ returnnull; } //當(dāng)前遍歷到的節(jié)點(diǎn)大于要找的節(jié)點(diǎn)，去左邊繼續(xù)找 if(root.val>key){ root.left=deleteNode(root.left,key); } //當(dāng)前遍歷到的節(jié)點(diǎn)小于要找的節(jié)點(diǎn)，去右邊繼續(xù)找 elseif(root.val