📘 題目敘述
給你一棵二元搜尋樹的根節點 root，以及一個整數 key。
請你從 BST 中刪除值等於 key 的節點，並回傳更新後的根節點 root。
刪除節點後，BST 的結構必須仍然有效。
你可以用任何方式回傳答案，只要結果仍是一棵有效的 BST 即可。
條件限制
- 樹中節點的數量在範圍
[0, 10^4] -10^5 <= Node.val <= 10^5- 樹中每個節點的值都互不相同
root是一棵有效的 BST-10^5 <= key <= 10^5
🧠 解題思路
這題我一樣先利用 BST 的性質去找到要刪的節點位置：
key < root->val就代表要刪的節點只可能在左子樹key > root->val就代表只可能在右子樹root->val == key才進入真正的刪除處理
真正刪除時，BST 會遇到三種情況：
- 要刪的節點沒有左子樹
代表它可以直接被右子樹取代 - 要刪的節點沒有右子樹
代表它可以直接被左子樹取代 - 左右子樹都存在
這種最麻煩，因為不能直接把其中一邊接上來，不然 BST 可能壞掉
我的做法是找右子樹中最小的節點（也就是中序後繼 in-order successor）來頂替目前節點的值
然後再去右子樹把那個「被拿來頂替的值」刪掉一次
這樣可以保證：
- 目前節點的值會變成「比左子樹都大、又是右子樹裡最小」的合法值
- 刪掉右子樹中的那個值後，整棵樹仍是 BST
所有變數
goal：當root同時有左右子樹時，我用它去找右子樹中最小的節點（中序後繼）
🪜 主要流程步驟
1. 先處理空樹
如果 root == nullptr，代表找不到要刪的節點，直接回傳 nullptr。
2. 用 BST 性質往下找 key
如果目前節點不是要刪的值，就只會往一邊遞迴：
root->val > key：去左子樹刪，並把結果接回root->leftroot->val < key：去右子樹刪，並把結果接回root->right
這樣遞迴回來時，整棵樹的連結也會被更新好。
3. 找到要刪的節點後，分三種刪除情況
如果 root->val == key，就進入刪除邏輯。
4. 沒有左子樹：直接用右子樹取代
如果 root->left 不存在，代表刪掉它後整棵樹要接回去的就是 root->right，所以直接回傳 root->right。
5. 沒有右子樹：直接用左子樹取代
如果 root->right 不存在，同理直接回傳 root->left。
6. 左右子樹都存在：用右子樹最小值頂替，再去刪掉那個值
這是核心步驟：
我先在右子樹找最左邊的節點：
goal = root->right- 一直
while (goal->left) goal = goal->left;
這樣 goal 就是右子樹裡最小的節點。
接著：
root->val = goal->val用這個值取代目前節點的值- 但這樣會造成右子樹裡還存在一個相同的值，所以我再做一次：
root->right = deleteNode(root->right, goal->val)- 把右子樹裡那個
goal->val的節點刪掉
最後 return root，整棵樹就會保持 BST 結構。
⏱️ 複雜度
- 時間複雜度：
O(h)h是樹高。搜尋要刪的節點是O(h)，如果遇到「左右子樹都有」的情況，還會再往右子樹一路找最小值並再刪一次，但仍然都只走高度等級，所以整體是O(h)。平衡 BST 是O(log n)，最壞鏈狀是O(n)。 - 空間複雜度：
O(h)
主要是遞迴呼叫堆疊的深度。
💻 程式碼實作
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) {
return nullptr;
}
if (root->val > key) {
root->left = deleteNode(root->left, key);
} else if (root->val < key) {
root->right = deleteNode(root->right, key);
} else {
if (!root->left) {
return root->right;
} else if (!root->right) {
return root->left;
} else {
TreeNode* goal = root->right;
while (goal->left) {
goal = goal->left;
}
root->val = goal->val;
root->right = deleteNode(root->right, goal->val);
}
}
return root;
}
};
🔗 題目連結
https://leetcode.com/problems/delete-node-in-a-bst/