Delete Node in a BST
題目描述
給定一棵 BST 的根節點 root 和一個值 key，刪除 key 對應的節點並回傳修改後的根節點。保證刪除後仍然是有效的 BST。
輸入: root = [5,3,6,2,4,null,7], key = 3
輸出: [5,4,6,2,null,null,7]
解釋: 3 有兩個子節點，用中序後繼 4 替換
輸入: root = [5,3,6,2,4,null,7], key = 0
輸出: [5,3,6,2,4,null,7]
解釋: 0 不在樹中，不做任何修改
解題思路
搜尋目標節點
key 小於 root.val 往左遞迴、大於往右遞迴，等於時進入刪除邏輯
Case 1: 葉節點
左右子樹都為 null，直接回傳 null 讓父節點斷開連結
Case 2: 單子節點
只有一邊子樹，回傳該子樹讓它直接頂替被刪節點的位置
Case 3: 雙子節點
找右子樹最左節點（中序後繼），用其值覆蓋當前節點，再遞迴刪除那個後繼節點
程式碼
C#
public class Solution {
public TreeNode DeleteNode(TreeNode root, int key) {
if (root == null) return null;
if (key < root.val) {
root.left = DeleteNode(root.left, key);
} else if (key > root.val) {
root.right = DeleteNode(root.right, key);
} else {
// 找到目標節點
if (root.left == null) return root.right; // Case 1 & 2
if (root.right == null) return root.left; // Case 2
// Case 3: 找右子樹最小值（中序後繼）
var successor = root.right;
while (successor.left != null) {
successor = successor.left;
}
root.val = successor.val; // 用後繼的值替換
root.right = DeleteNode(root.right, successor.val); // 刪除後繼
}
return root;
}
}TypeScript
function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
if (!root) return null;
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
if (!root.left) return root.right; // Case 1 & 2
if (!root.right) return root.left; // Case 2
// Case 3: 找右子樹最小值
let successor = root.right;
while (successor.left) {
successor = successor.left;
}
root.val = successor.val;
root.right = deleteNode(root.right, successor.val);
}
return root;
}Python
def deleteNode(root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root:
return None
if key < root.val:
root.left = deleteNode(root.left, key)
elif key > root.val:
root.right = deleteNode(root.right, key)
else:
if not root.left:
return root.right # Case 1 & 2
if not root.right:
return root.left # Case 2
# Case 3: 找右子樹最小值
successor = root.right
while successor.left:
successor = successor.left
root.val = successor.val
root.right = deleteNode(root.right, successor.val)
return root複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(h) | O(h) |
h 是樹高。平衡 BST 中 h = O(log n)。Time O(h) 是因為搜尋目標節點走 h 步，找後繼最多再走 h 步，刪後繼又走 h 步，總共 O(3h) = O(h)。Space O(h) 是遞迴 call stack 深度。
邊界情況
- key 不在樹中：遞迴到 null 回傳 null，整棵樹不變
- 刪除根節點：和刪除任何節點的邏輯相同，但回傳值會成為新的 root
- 後繼是直接右子節點：右子樹的最小值就是 root.right 本身（沒有左子），此時用 root.right.val 替換後刪除 root.right
圖解
圖表展示了刪除節點 3 的過程：節點 3 有左子 2 和右子 4（Case 3）。右子樹最小值是 4（中序後繼），用 4 的值覆蓋 3，再刪除原本的節點 4。最終 BST 性質不變。
進階觀點
💡面試追問
Q: 中序後繼和中序前驅有什麼差別？選哪個？ A: 中序後繼是右子樹最小值，中序前驅是左子樹最大值。兩者都能維持 BST 性質，效果相同。選擇任一即可，面試中提到兩種方案展示全面性。
Q: 值替換和純指針操作的取捨？ A: 值替換程式碼簡潔（5 行 vs 15+ 行），但假設節點只有一個值。如果節點有額外資料（如指向其他結構的引用），值替換會破壞外部引用。此時必須用純指針操作 — 把後繼節點「摘下來」放到被刪位置，調整左右子樹指針。
變體題：LC 669 Trim a BST（刪除範圍外的節點）、LC 1038 BST to Greater Sum Tree。
理解測驗
🤔 刪除有兩個子節點的 BST 節點時，為什麼選右子樹的最小值來替換？
🤔 中序後繼一定沒有左子節點嗎？