遞歸法

1、確定遞歸函數的參數和返回值
說到遞歸函數的返回值，在?叉樹：搜索樹中的插?操作中通過遞歸返回值來加?新節點， 這?也可以通過遞歸返回值刪除節點。

TreeNode* deleteNode(TreeNode* root,int key);

2、確定終止條件
遇到空返回，說明沒有找到刪除的節點

if(root==nullptr) return root;

3、確定單層遞歸的邏輯
刪除節點會遇到5種情況：
第?種情況：沒找到刪除的節點，遍歷到空節點直接返回了

找到刪除的節點：
第?種情況：左右孩?都為空（葉?節點），直接刪除節點， 返回NULL為根節點
第三種情況：刪除節點的左孩?為空，右孩?不為空，刪除節點，右孩?補位，返回右孩?為根節點
第四種情況：刪除節點的右孩?為空，左孩?不為空，刪除節點，左孩?補位，返回左孩?為根節點
第五種情況：左右孩?節點都不為空，則將刪除節點的左?樹頭結點（左孩?）放到刪除節點的右?樹的最左?節點的左孩?上，返回刪除節點右孩?為新的根節點。

if (root->val == key) {// 第二種情況：左右孩子都為空（葉子節點），直接刪除節點， 返回NULL為根節點// 第三種情況：其左孩子為空，右孩子不為空，刪除節點，右孩子補位 ，返回右孩子為根節點if (root->left == nullptr) return root->right; // 第四種情況：其右孩子為空，左孩子不為空，刪除節點，左孩子補位，返回左孩子為根節點else if (root->right == nullptr) return root->left; // 第五種情況：左右孩子節點都不為空，則將刪除節點的左子樹放到刪除節點的右子樹的最左面節點的左孩子的位置// 并返回刪除節點右孩子為新的根節點。else { TreeNode* cur = root->right; // 找右子樹最左面的節點while(cur->left != nullptr) { cur = cur->left;}cur->left = root->left; // 把要刪除的節點（root）左子樹放在cur的左孩子的位置TreeNode* tmp = root; // 把root節點保存一下，下面來刪除root = root->right; // 返回舊root的右孩子作為新rootdelete tmp; // 釋放節點內存（這里不寫也可以，但C++最好手動釋放一下吧）return root;} }

完整遞歸

class Solution { public:TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return root; // 第一種情況：沒找到刪除的節點，遍歷到空節點直接返回了if(root->val==key){//5皇帝要殺一個犯錯的士兵3，士兵被送入斷頭臺(delete函數)，在臨死之前，士兵把自己的孩子返回交給皇帝來繼承自己的位置if(root->left==nullptr) return root->right;if(root->right==nullptr) return root->left;else {TreeNode* cur=root->right;while(cur->left!=nullptr){cur=cur->left;}cur->left=root->left;return root->right;}} //皇帝root要找到犯錯士兵key并處置它if(key<root->val) root->left=deleteNode(root->left,key);if(key>root->val) root->right=deleteNode(root->right,key);return root;} };

大家畫圖就會發現上面的代碼其實是有數據冗余的。那么我們可以接著優化下：

class Solution { public:TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return root; // 第一種情況：沒找到刪除的節點，遍歷到空節點直接返回了if (root->val == key) {// 第二種情況：左右孩子都為空（葉子節點），直接刪除節點， 返回NULL為根節點//可省略if(root->left==nullptr&&root->right==nullptr) return NULL;// 第三種情況：其左孩子為空，右孩子不為空，刪除節點，右孩子補位 ，返回右孩子為根節點if (root->left == nullptr) return root->right; // 第四種情況：其右孩子為空，左孩子不為空，刪除節點，左孩子補位，返回左孩子為根節點else if (root->right == nullptr) return root->left; // 第五種情況：左右孩子節點都不為空，則將刪除節點的左子樹放到刪除節點的右子樹的最左面節點的左孩子的位置// 并返回刪除節點右孩子為新的根節點。else { TreeNode* cur = root->right; // 找右子樹最左面的節點while(cur->left != nullptr) { cur = cur->left;}cur->left = root->left; // 把要刪除的節點（root）左子樹放在cur的左孩子的位置TreeNode* tmp = root; // 把root節點保存一下，下面來刪除root = root->right; // 返回舊root的右孩子作為新rootdelete tmp; // 釋放節點內存（這里不寫也可以，但C++最好手動釋放一下吧）return root;}}if (root->val > key) root->left = deleteNode(root->left, key);if (root->val < key) root->right = deleteNode(root->right, key);return root;} };

最終版

class Solution { public:TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return root; // 第一種情況：沒找到刪除的節點，遍歷到空節點直接返回了if(root->val==key){//5皇帝要殺一個犯錯的士兵3，士兵被送入斷頭臺(delete函數)，在臨死之前，士兵把自己的孩子返回交給皇帝來繼承自己的位置if(root->left==nullptr) {TreeNode* temp=root;root=root->right;delete temp; return root;}if(root->right==nullptr) {TreeNode* temp=root;root=root->left;delete temp;return root;}else { TreeNode* cur = root->right; // 找右子樹最左面的節點while(cur->left != nullptr) { cur = cur->left;}cur->left = root->left; // 把要刪除的節點（root）左子樹放在cur的左孩子的位置TreeNode* tmp = root; // 把root節點保存一下，下面來刪除root = root->right; // 返回舊root的右孩子作為新rootdelete tmp; // 釋放節點內存（這里不寫也可以，但C++最好手動釋放一下吧）return root;}}if (root->val > key) root->left = deleteNode(root->left, key);if (root->val < key) root->right = deleteNode(root->right, key);return root;} };

總結

以上是生活随笔為你收集整理的删除二叉搜索树中的节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。