來自公眾號：五分鐘學(xué)算法
作者P.yh
今天分享的題目來源于 LeetCode 第 450 號問題：刪除二叉搜索樹中的節(jié)點丸边。雖然它的難度是 中等叠必，但實際上很好理解，請往下看妹窖！
題目描述
給定一個二叉搜索樹的根節(jié)點 root 和一個值 key纬朝，刪除二叉搜索樹中的 key 對應(yīng)的節(jié)點，并保證二叉搜索樹的性質(zhì)不變骄呼。返回二叉搜索樹（有可能被更新）的根節(jié)點的引用共苛。
一般來說，刪除節(jié)點可分為兩個步驟：
首先找到需要刪除的節(jié)點蜓萄；
如果找到了隅茎，刪除它。
說明：要求算法時間復(fù)雜度為 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
題目解析
在二叉搜索樹上刪除一個節(jié)點跃捣，這道題目有一個隱含的條件漱牵，就是樹上節(jié)點的值不重復(fù)夺蛇。
另外題目還要求時間復(fù)雜度需要保證 O(h) 這里的 h 表示的是二叉樹的高度疚漆。
其實這個題目是分成兩個步驟的，第一個是找到對應(yīng)的節(jié)點刁赦，第二個是刪除節(jié)點娶聘。
因為是二叉搜索樹，對于樹上每個節(jié)點來說甚脉，其 右子樹的節(jié)點都要大于其左子樹的節(jié)點丸升，那么要找對應(yīng)節(jié)點，我們可以從根節(jié)點開始牺氨，一路比較狡耻，大的話就去右邊找，小的話就去左邊找猴凹，這樣每次我們都往下夷狰，可以保證時間復(fù)雜度是 O(h)。
當(dāng)我們找到了要刪除的節(jié)點郊霎，在刪除這一步就會有很多的細節(jié)沼头，主要是因為我們需要調(diào)整余下的結(jié)構(gòu)，以維持二叉搜索樹的性質(zhì)书劝。
針對這個問題进倍，我們可以分情況討論：
5
/ \
3 6
/ \ \
2 4 7
/ \
1 8
情況 1：當(dāng)刪除的節(jié)點沒有左右子樹，比如上圖的 4购对、8猾昆、1
這時直接刪除即可，樹依舊可以保持二叉搜索樹的性質(zhì)情況 2：當(dāng)刪除的節(jié)點有左子樹沒有右子樹骡苞，比如上圖的 2
這時我們只需要將整個左子樹移到當(dāng)前位置即可
也就是將左子樹的根節(jié)點放到刪除節(jié)點的位置垂蜗，其余不變情況 3：當(dāng)刪除的節(jié)點沒有左子樹有右子樹，比如上圖的 6烙如、7
這時我們只需要將整個右子樹移到當(dāng)前位置即可
也就是將右子樹的根節(jié)點放到刪除節(jié)點的位置么抗，其余不變情況 4：當(dāng)刪除的節(jié)點既有左子樹又有右子樹，比如上圖的 5亚铁、3
這時就有兩種方法供選擇：
去到左子樹中蝇刀，找到值最大節(jié)點，將右子樹全部移到這個節(jié)點下
去到右子樹中徘溢，找到值最小節(jié)點吞琐，將左子樹全部移到這個節(jié)點下
通過上面的討論分析捆探，我們有了大致的思路。在實現(xiàn)方面站粟，我們可以借助遞歸來巧妙地達到刪除對應(yīng)節(jié)點的目的黍图。
圖片描述
參考代碼
//五分鐘學(xué)算法
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
// 當(dāng)前遍歷到的節(jié)點大于要找的節(jié)點，去左邊繼續(xù)找
if (root.val > key) {
root.left = deleteNode(root.left, key);
}
// 當(dāng)前遍歷到的節(jié)點小于要找的節(jié)點奴烙，去右邊繼續(xù)找
else if (root.val < key) {
root.right = deleteNode(root.right, key);
}
// 找到要刪除的節(jié)點助被，進行刪除操作
else {
// 情況 1 & 2
if (root.right == null) {
return root.left;
}
// 情況 3
if (root.left == null) {
return root.right;
}
// 去到刪除節(jié)點的右子樹，找到值最小的節(jié)點
TreeNode rightSmallest = root.right;
while (rightSmallest.left != null) {
rightSmallest = rightSmallest.left;
}
// 將刪除節(jié)點的左子樹全部移到這個節(jié)點下
rightSmallest.left = root.left;
// 返回右子樹的根節(jié)點切诀，放到當(dāng)前刪除節(jié)點的位置
return root.right;
}
return root;
}
