450. Delete Node in a BST

──────────────────────────────────────────────────────────────────────

450. Delete Node in a BST

在 BST 中刪掉值等於 key 的節點，刪完之後仍然要是一棵合法的 BST。

思路

題目給的條件看起來很簡單，好像只要做兩件事：

1. 遍歷找到該節點
2. 刪掉他

第一步跟 700 一模一樣，沒有難度。難的全在第二步 —— 和插入不同，刪掉一個節點之後，被剪斷的兩棵子樹要接回樹上，而且要維持 BST 的結構。

直接把左子樹接上去為什麼不行

第一個想法是：既然 BST 保證了左子樹全部小於右子樹，那把左子樹的根節點接上來當新的根，再把原本的右子樹接到它下面就好了吧？

問題馬上來 —— 要是原本的左子樹自己就有右子樹怎麼辦？ 那個位置已經被佔住了。往下找一層，又會遇到同樣的問題，處理子樹的子樹、再處理子樹的子樹的子樹⋯⋯本來想找終止條件，結果變成沒完沒了。

這一題我想的時候的確想了滿久。後來是退一步想：如果要接上來的那個節點，本身沒有任何子樹就好了。

找一個「不會卡住」的替身

那要找誰？把兩個事實放在一起：

1. 右子樹的最小值，根據 BST 的定義，永遠比左子樹的最大值大 —— 所以它有資格當新的根
2. 右子樹的最小值一定在右子樹的最左邊 —— 而一路往左走到底的節點，不可能有左子樹（有的話就不是最左了）

第 2 點正是我們要的性質：這個替身最多只有一個右子樹，不會有「兩邊都被佔住」的問題。

這個節點叫做中序後繼（inorder successor）—— 中序遍歷中排在目標節點後面的那一個。用它頂上去，中序序列只是少了一個元素，順序完全沒被打亂，所以結果一定還是合法的 BST。

用「換值」取代「搬節點」

找到替身之後，直覺的步驟是：

1. 把右子樹最左的葉子拿出來當新的根節點
2. 把原先的左子樹接上這個新的根節點
3. 把剩餘的右子樹接上這個新的根節點
4. 把這個新根接回原先的樹

第 4 步很煩 —— 得記住原本是誰連著這個位置。但其實不需要真的搬動節點，把值複製過來就好：

1. 找到右子樹最左的葉子，把它的值覆蓋掉當前節點的值
2. 此時左子樹完全不用動
3. 右子樹也還在原位
4. 剩下的工作是「把右子樹裡那個原本的最小值刪掉」—— 這就是同一個問題的子問題，遞迴下去

而這個遞迴一定馬上結束：那個後繼節點沒有左子樹，所以進到遞迴之後會直接命中「只有一個子樹」的簡單情況，不會再往下滾。

於是刪除只剩三種情況：

情況	怎麼處理
沒有左子樹	直接回傳右子樹（葉節點時剛好回傳 None）
沒有右子樹	直接回傳左子樹
兩邊都有	用中序後繼的值覆蓋，再遞迴刪掉那個後繼

前兩種涵蓋了「葉節點」的情況，不用另外寫。

解題方向

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

class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root: return root
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
        elif root.val == key:
            if not root.left:
                return root.right
            if not root.right:
                return root.left
            smallestOnRight = root.right
            while smallestOnRight.left:
                smallestOnRight = smallestOnRight.left
            root.val = smallestOnRight.val
            root.right = self.deleteNode(root.right, smallestOnRight.val)
        return root

root.left = self.deleteNode(root.left, key) 這個寫法是整題的骨架，跟 701 插入 用的是同一招：

遞迴回傳「處理完之後這棵子樹的新根」，由父節點自己重新接上去。

這樣就不需要維護 parent 指標，也不需要特別處理「被刪的是不是根節點」—— 根節點的情況就是最外層那個 return root 或 return root.right。所有會改變樹結構的題目都適用這個慣用法。

if not root: return root 同時處理了「樹是空的」和「key 根本不在樹裡」兩件事 —— 找不到就原封不動地回傳。

補充

用左子樹的最大值（中序前驅）也可以，邏輯完全對稱：一路往右走到底的節點不可能有右子樹，同樣不會卡住。

p = root.left
while p.right:
    p = p.right
root.val = p.val
root.left = self.deleteNode(root.left, p.val)

兩種選法都對，結果的樹形不一樣但都合法。真實的 BST 實作有時會交替使用兩者，避免長期只從一邊刪造成樹越來越歪。

BST 家族的共同骨架都是「比較 → 往一邊走」，差別在走到底之後做什麼：

題目	走到底之後
700. Search in a BST	回傳節點
701. Insert into a BST	在空位掛上新節點
450	用後繼（或前驅）補位
235. LCA of a BST	走到分岔點就停
270. Closest BST Value	一路記錄最接近的值

「中序後繼」這個概念在別的地方也會出現：98. Validate BST（中序序列嚴格遞增）、173. BST Iterator（next() 就是在求中序後繼）、230. Kth Smallest in a BST。整理見 Tree 遍歷模板。

複雜度

• 時間 $O(h)$ — 往下找目標走 $O(h)$，找後繼再走 $O(h)$，遞迴刪後繼那一層是常數，加起來還是 $O(h)$
• 空間 $O(h)$ — 遞迴堆疊

其中 h 是樹高。平衡時是 $O(\log n)$，退化成一條鏈時是 $O(n)$。

值得注意的是刪除不會讓樹重新平衡 —— 這題只保證結果是合法的 BST，不保證它不會越刪越歪。真正的自平衡結構（AVL、紅黑樹）會在刪除後做旋轉，那是另一個層次的東西。