一、題目內容

題目要求刪除二叉搜索樹（BST）中值為 key 的節點，并保證刪除后二叉搜索樹的性質不變。返回刪除節點后的二叉搜索樹的根節點的引用。一般來說，刪除節點可分為兩個步驟：首先找到需要刪除的節點；如果找到了，刪除它。

二、題目分析

（一）輸入和輸出

輸入：二叉搜索樹的根節點 root 和待刪除的值 key。

輸出：刪除指定值節點后二叉搜索樹的根節點。

（二）遞歸函數 deleteNode 的邏輯

基本情況：如果當前節點為空（root == NULL），說明沒有找到需要刪除的節點，直接返回 NULL。

如果當前節點的值等于 key（root->val == key），則需要根據當前節點的子節點情況來決定如何刪除：

1. 如果當前節點是葉子節點（root->left == NULL && root->right == NULL），直接刪除當前節點并返回 NULL。

2. 如果當前節點只有一個右子節點（root->left == NULL && root->right != NULL），刪除當前節點并返回其右子節點。

3. 如果當前節點只有一個左子節點（root->left != NULL && root->right == NULL），刪除當前節點并返回其左子節點。

4. 如果當前節點既有左子節點又有右子節點，找到當前節點右子樹的最左節點（即右子樹中的最小值節點），將其左子樹連接到該最左節點的左子樹上，然后刪除當前節點并返回其右子節點。

遞歸邏輯：如果當前節點的值大于 key（root->val > key），則遞歸地在左子樹中刪除 key 對應的節點；如果當前節點的值小于 key（root->val < key），則遞歸地在右子樹中刪除 key 對應的節點。遞歸返回后，將返回的子樹節點賦值給當前節點的左或右子節點。

三、解題要點

（一）二叉搜索樹的定義

二叉搜索樹是一種特殊的二叉樹，其性質是：對于任意節點，其左子樹上所有節點的值都小于該節點的值，其右子樹上所有節點的值都大于該節點的值。這一性質是刪除操作的基礎，刪除操作需要保持這一性質不變。

（二）刪除操作的性質

刪除操作需要保持二叉搜索樹的性質不變。刪除節點后，樹的結構需要重新調整，以確保仍然滿足二叉搜索樹的性質。

（三）解題思路

1.基本情況

如果當前節點為空（root == NULL），說明沒有找到需要刪除的節點，直接返回 NULL。這是遞歸的終止條件。

2.遞歸邏輯

比較當前節點值與待刪除值：

如果當前節點的值等于 key（root->val == key），根據當前節點的子節點情況來決定如何刪除。

如果當前節點的值大于 key（root->val > key），則遞歸地在左子樹中刪除 key 對應的節點。

如果當前節點的值小于 key（root->val < key），則遞歸地在右子樹中刪除 key 對應的節點。

更新子樹：遞歸返回后，將返回的子樹節點賦值給當前節點的左或右子節點。這一步確保了遞歸返回后，當前節點的子樹被正確更新。

3.遞歸返回

遞歸返回時，返回當前節點。這一步確保了遞歸調用的正確性，使得每次遞歸返回后，當前節點的狀態被正確恢復，不會影響后續的遞歸調用。

四、代碼解答

class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {// 如果當前節點為空，直接返回 NULLif (root == NULL) return NULL;// 如果當前節點的值等于 key，根據子節點情況決定如何刪除if (root->val == key) {// 如果當前節點是葉子節點，直接刪除并返回 NULLif (root->left == NULL && root->right == NULL) {delete root;return NULL;}// 如果當前節點只有一個右子節點，刪除當前節點并返回其右子節點else if (root->left == NULL && root->right != NULL) {TreeNode* temp = root->right;delete root;return temp;}// 如果當前節點只有一個左子節點，刪除當前節點并返回其左子節點else if (root->left != NULL && root->right == NULL) {TreeNode* temp = root->left;delete root;return temp;}// 如果當前節點既有左子節點又有右子節點else {// 找到當前節點右子樹的最左節點TreeNode* cur = root->right;while (cur->left != NULL) {cur = cur->left;}// 將當前節點的左子樹連接到最左節點的左子樹上cur->left = root->left;// 刪除當前節點并返回其右子節點TreeNode* temp = root->right;delete root;return temp;}}// 如果當前節點的值大于 key，遞歸地在左子樹中刪除 key 對應的節點if (root->val > key) {root->left = deleteNode(root->left, key);}// 如果當前節點的值小于 key，遞歸地在右子樹中刪除 key 對應的節點else {root->right = deleteNode(root->right, key);}// 返回當前節點return root;}
};

五、詳細注釋

（一）遞歸函數 deleteNode

基本情況：如果當前節點為空，直接返回 NULL。

如果當前節點的值等于 key，根據當前節點的子節點情況來決定如何刪除。

遞歸邏輯：如果當前節點的值大于 key，遞歸地在左子樹中刪除 key 對應的節點；如果當前節點的值小于 key，遞歸地在右子樹中刪除 key 對應的節點。遞歸返回后，將返回的子樹節點賦值給當前節點的左或右子節點。

六、回溯和遞歸的詳細解釋

（一）遞歸

遞歸是一種函數調用自身的方法，用于解決復雜問題。在本題中，遞歸用于逐層檢查每個節點，找到需要刪除的節點，并根據情況調整樹的結構。遞歸的核心思想是將問題分解為更小的子問題，通過解決子問題來解決原問題。

（二）終止條件

遞歸的終止條件是當前節點為空，此時直接返回 NULL。這是遞歸的出口，確保遞歸不會無限進行下去。

（三）回溯

在遞歸調用返回后，通過返回值恢復到當前節點的狀態，確保每次遞歸返回后，狀態正確，不會影響后續的遞歸調用。

在本題中，回溯的過程主要體現在以下幾個方面：

1. 遞歸調用的返回值：每個遞歸分支都會返回一個節點，這個節點可以是刪除操作后的子樹的根節點，也可以是 NULL。

2. 返回值的處理：在每個遞歸調用返回后，當前節點會根據返回值來決定下一步的操作：

   • 如果當前節點的值大于 key，將返回值賦值給當前節點的左子節點。

   • 如果當前節點的值小于 key，將返回值賦值給當前節點的右子節點。

（四）遞歸調用的詳細過程

1. 初始調用：從根節點開始調用 deleteNode(root, key)。

2. 遞歸調用：如果 root->val > key，遞歸調用 deleteNode(root->left, key)；如果 root->val < key，遞歸調用 deleteNode(root->right, key)。

3. 終止條件：當遞歸調用到達一個空節點時，直接返回 NULL。

4. 回溯過程：遞歸返回后，將返回的子樹節點賦值給當前節點的左或右子節點。遞歸返回到上一層調用，繼續處理上一層的節點，直到返回到根節點。

（五）代碼執行過程示例

假設我們有一個二叉搜索樹，根節點為 root，值為 5，其左子節點值為 3，右子節點值為 7。現在要刪除值為 3 的節點。

1. 初始調用：deleteNode(root, 3)。

2. 當前節點值為 5，3 < 5，遞歸調用 deleteNode(root->left, 3)。

3. 遞歸調用：deleteNode(root->left, 3)。

4. 當前節點值為 3，3 == 3，進入刪除邏輯：

   • 當前節點只有一個左子節點，刪除當前節點并返回其左子節點。

5. 回溯過程：

   • 返回到 root，將返回的左子節點