[[421470]]

二叉搜索樹刪除節點就涉及到結構調整了!

刪除二叉搜索樹中的節點

題目鏈接：https://leetcode-cn.com/problems/delete-node-in-a-bst/

給定一個二叉搜索樹的根節點 root 和一個值 key，刪除二叉搜索樹中的 key 對應的節點，并保證二叉搜索樹的性質不變。返回二叉搜索樹(有可能被更新)的根節點的引用。

一般來說，刪除節點可分為兩個步驟：

首先找到需要刪除的節點;如果找到了，刪除它。說明：要求算法時間復雜度為 O(h)，h 為樹的高度。

示例:

思路

搜索樹的節點刪除要比節點增加復雜的多，有很多情況需要考慮，做好心里準備。

遞歸

遞歸三部曲：

• 確定遞歸函數參數以及返回值

說道遞歸函數的返回值，在二叉樹：搜索樹中的插入操作中通過遞歸返回值來加入新節點， 這里也可以通過遞歸返回值刪除節點。

代碼如下：

TreeNode* deleteNode(TreeNode* root, int key) 

• 確定終止條件

遇到空返回，其實這也說明沒找到刪除的節點，遍歷到空節點直接返回了

if (root == nullptr) return root; 

• 確定單層遞歸的邏輯

這里就把平衡二叉樹中刪除節點遇到的情況都搞清楚。

有以下五種情況：

• 第一種情況：沒找到刪除的節點，遍歷到空節點直接返回了
  • 找到刪除的節點
• 第二種情況：左右孩子都為空(葉子節點)，直接刪除節點， 返回NULL為根節點
• 第三種情況：刪除節點的左孩子為空，右孩子不為空，刪除節點，右孩子補位，返回右孩子為根節點
• 第四種情況：刪除節點的右孩子為空，左孩子不為空，刪除節點，左孩子補位，返回左孩子為根節點
• 第五種情況：左右孩子節點都不為空，則將刪除節點的左子樹頭結點(左孩子)放到刪除節點的右子樹的最左面節點的左孩子上，返回刪除節點右孩子為新的根節點。

第五種情況有點難以理解，看下面動畫：

刪除二叉搜索樹中的節點

動畫中顆二叉搜索樹中，刪除元素7， 那么刪除節點(元素7)的左孩子就是5，刪除節點(元素7)的右子樹的最左面節點是元素8。

將刪除節點(元素7)的左孩子放到刪除節點(元素7)的右子樹的最左面節點(元素8)的左孩子上，就是把5為根節點的子樹移到了8的左孩子的位置。

要刪除的節點(元素7)的右孩子(元素9)為新的根節點。.

這樣就完成刪除元素7的邏輯，最好動手畫一個圖，嘗試刪除一個節點試試。

代碼如下：

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的右孩子作為新root 
        delete tmp;             // 釋放節點內存（這里不寫也可以，但C++最好手動釋放一下吧） 
        return root; 
    } 
} 

這里相當于把新的節點返回給上一層，上一層就要用 root->left 或者 root->right接住，代碼如下：

if (root->val > key) root->left = deleteNode(root->left, key); 
if (root->val < key) root->right = deleteNode(root->right, key); 
return root; 

整體代碼如下：(注釋中：情況1，2，3，4，5和上面分析嚴格對應)

class Solution { 
public: 
    TreeNode* deleteNode(TreeNode* root, int key) { 
        if (root == nullptr) return root; // 第一種情況：沒找到刪除的節點，遍歷到空節點直接返回了 
        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的右孩子作為新root 
                delete 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; 
    } 
}; 

普通二叉樹的刪除方式

這里我在介紹一種通用的刪除，普通二叉樹的刪除方式(沒有使用搜索樹的特性，遍歷整棵樹)，用交換值的操作來刪除目標節點。

代碼中目標節點(要刪除的節點)被操作了兩次：

• 第一次是和目標節點的右子樹最左面節點交換。
• 第二次直接被NULL覆蓋了。

思路有點繞，感興趣的同學可以畫圖自己理解一下。

代碼如下：(關鍵部分已經注釋)

class Solution { 
public: 
    TreeNode* deleteNode(TreeNode* root, int key) { 
        if (root == nullptr) return root; 
        if (root->val == key) { 
            if (root->right == nullptr) { // 這里第二次操作目標值：最終刪除的作用 
                return root->left; 
            } 
            TreeNode *cur = root->right; 
            while (cur->left) { 
                cur = cur->left; 
            } 
            swap(root->val, cur->val); // 這里第一次操作目標值：交換目標值其右子樹最左面節點。 
        } 
        root->left = deleteNode(root->left, key); 
        root->right = deleteNode(root->right, key); 
        return root; 
    } 
}; 

這個代碼是簡短一些，思路也巧妙，但是不太好想，實操性不強，推薦第一種寫法!

迭代法

刪除節點的迭代法還是復雜一些的，但其本質我在遞歸法里都介紹了，最關鍵就是刪除節點的操作(動畫模擬的過程)

代碼如下：

class Solution { 
private: 
    // 將目標節點（刪除節點）的左子樹放到 目標節點的右子樹的最左面節點的左孩子位置上 
    // 并返回目標節點右孩子為新的根節點 
    // 是動畫里模擬的過程 
    TreeNode* deleteOneNode(TreeNode* target) { 
        if (target == nullptr) return target; 
        if (target->right == nullptr) return target->left; 
        TreeNode* cur = target->right; 
        while (cur->left) { 
            cur = cur->left; 
        } 
        cur->left = target->left; 
        return target->right; 
    } 
public: 
    TreeNode* deleteNode(TreeNode* root, int key) { 
        if (root == nullptr) return root; 
        TreeNode* cur = root; 
        TreeNode* pre = nullptr; // 記錄cur的父節點，用來刪除cur 
        while (cur) { 
            if (cur->val == key) break; 
            pre = cur; 
            if (cur->val > key) cur = cur->left; 
            else cur = cur->right; 
        } 
        if (pre == nullptr) { // 如果搜索樹只有頭結點 
            return deleteOneNode(cur); 
        } 
        // pre 要知道是刪左孩子還是右孩子 
        if (pre->left && pre->left->val == key) { 
            pre->left = deleteOneNode(cur); 
        } 
        if (pre->right && pre->right->val == key) { 
            pre->right = deleteOneNode(cur); 
        } 
        return root; 
    } 
}; 

總結

讀完本篇，大家會發現二叉搜索樹刪除節點比增加節點復雜的多。

因為二叉搜索樹添加節點只需要在葉子上添加就可以的，不涉及到結構的調整，而刪除節點操作涉及到結構的調整。

這里我們依然使用遞歸函數的返回值來完成把節點從二叉樹中移除的操作。

這里最關鍵的邏輯就是第五種情況(刪除一個左右孩子都不為空的節點)，這種情況一定要想清楚。

而且就算想清楚了，對應的代碼也未必可以寫出來，所以這道題目即考察思維邏輯，也考察代碼能力。

遞歸中我給出了兩種寫法，推薦大家學會第一種(利用搜索樹的特性)就可以了，第二種遞歸寫法其實是比較繞的。

最后我也給出了相應的迭代法，就是模擬遞歸法中的邏輯來刪除節點，但需要一個pre記錄cur的父節點，方便做刪除操作。

迭代法其實不太容易寫出來，所以如果是初學者的話，徹底掌握第一種遞歸寫法就夠了。

其他語言版本

Java

class Solution { 
    public TreeNode deleteNode(TreeNode root, int key) { 
        root = delete(root,key); 
        return root; 
    } 
 
    private TreeNode delete(TreeNode root, int key) { 
        if (root == null) return null; 
 
        if (root.val > key) { 
            root.left = delete(root.left,key); 
        } else if (root.val < key) { 
            root.right = delete(root.right,key); 
        } else { 
            if (root.left == null) return root.right; 
            if (root.right == null) return root.left; 
            TreeNode tmp = root.right; 
            while (tmp.left != null) { 
                tmp = tmp.left; 
            } 
            root.val = tmp.val; 
            root.right = delete(root.right,tmp.val); 
        } 
        return root; 
    } 
} 

Python

class Solution: 
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode: 
        if not root: return root  #第一種情況：沒找到刪除的節點，遍歷到空節點直接返回了 
        if root.val == key: 
            if not root.left and not root.right:  #第二種情況：左右孩子都為空（葉子節點），直接刪除節點， 返回NULL為根節點 
                del root 
                return None 
            if not root.left and root.right:  #第三種情況：其左孩子為空，右孩子不為空，刪除節點，右孩子補位 ，返回右孩子為根節點 
                tmp = root 
                root = root.right 
                del tmp 
                return root 
            if root.left and not root.right:  #第四種情況：其右孩子為空，左孩子不為空，刪除節點，左孩子補位，返回左孩子為根節點 
                tmp = root 
                root = root.left 
                del tmp 
                return root 
            else:  #第五種情況：左右孩子節點都不為空，則將刪除節點的左子樹放到刪除節點的右子樹的最左面節點的左孩子的位置 
                v = root.right 
                while v.left: 
                    v = v.left 
                v.left = root.left 
                tmp = root 
                root = root.right 
                del tmp 
                return root 
        if root.val > key: root.left = self.deleteNode(root.left,key)  #左遞歸 
        if root.val < key: root.right = self.deleteNode(root.right,key)  #右遞歸 
        return root 

本文轉載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關注。轉載本文請聯系代碼隨想錄公眾號。