---
title: "450. Delete Node in a BST"
url: "https://laigary.com/interview/coding/450-delete-node-in-a-bst"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-28"
tags: ["Tree", "Classic", "Binary Search Tree"]
---

# 450. Delete Node in a BST

[450\. Delete Node in a BST](https://leetcode.com/problems/delete-node-in-a-bst/)

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

## 思路

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

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

第一步跟 [700](/interview/coding/700-search-in-a-binary-search-tree) 一模一樣，沒有難度。難的全在第二步 —— 和插入不同，刪掉一個節點之後，被剪斷的兩棵子樹要接回樹上，而且要維持 BST 的結構。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

於是刪除只剩三種情況：

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

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

## 解題方向

```python
# 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 插入](/interview/coding/701-insert-into-a-binary-search-tree) 用的是同一招：

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

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

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

## 補充

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

```python
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](/interview/coding/700-search-in-a-binary-search-tree) | 回傳節點 |
| [701. Insert into a BST](/interview/coding/701-insert-into-a-binary-search-tree) | 在空位掛上新節點 |
| 450 | 用後繼（或前驅）補位 |
| [235. LCA of a BST](/interview/coding/235-lowest-common-ancestor-of-a-binary-search-tree) | 走到分岔點就停 |
| [270. Closest BST Value](/interview/coding/270-closest-binary-search-tree-value) | 一路記錄最接近的值 |

**「中序後繼」這個概念在別的地方也會出現**：[98. Validate BST](/interview/coding/98-validate-binary-search-tree)（中序序列嚴格遞增）、[173. BST Iterator](/interview/coding/173-binary-search-tree-iterator)（`next()` 就是在求中序後繼）、[230. Kth Smallest in a BST](/interview/coding/230-kth-smallest-element-in-a-bst)。整理見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。

## 複雜度

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

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

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