[[421470]]

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

刪除二叉搜索樹中的節(jié)點

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

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

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

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

示例:

思路

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

遞歸

遞歸三部曲：

• 確定遞歸函數(shù)參數(shù)以及返回值

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

代碼如下：

TreeNode* deleteNode(TreeNode* root, int key) 

• 確定終止條件

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

if (root == nullptr) return root; 

• 確定單層遞歸的邏輯

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

有以下五種情況：

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

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

刪除二叉搜索樹中的節(jié)點

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

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

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

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

代碼如下：

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

這里相當于把新的節(jié)點返回給上一層，上一層就要用 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; // 第一種情況：沒找到刪除的節(jié)點，遍歷到空節(jié)點直接返回了 
        if (root->val == key) { 
            // 第二種情況：左右孩子都為空（葉子節(jié)點），直接刪除節(jié)點， 返回NULL為根節(jié)點 
            // 第三種情況：其左孩子為空，右孩子不為空，刪除節(jié)點，右孩子補位 ，返回右孩子為根節(jié)點 
            if (root->left == nullptr) return root->right; 
            // 第四種情況：其右孩子為空，左孩子不為空，刪除節(jié)點，左孩子補位，返回左孩子為根節(jié)點 
            else if (root->right == nullptr) return root->left; 
            // 第五種情況：左右孩子節(jié)點都不為空，則將刪除節(jié)點的左子樹放到刪除節(jié)點的右子樹的最左面節(jié)點的左孩子的位置 
            // 并返回刪除節(jié)點右孩子為新的根節(jié)點。 
            else { 
                TreeNode* cur = root->right; // 找右子樹最左面的節(jié)點 
                while(cur->left != nullptr) { 
                    cur = cur->left; 
                } 
                cur->left = root->left; // 把要刪除的節(jié)點（root）左子樹放在cur的左孩子的位置 
                TreeNode* tmp = root;   // 把root節(jié)點保存一下，下面來刪除 
                root = root->right;     // 返回舊root的右孩子作為新root 
                delete tmp;             // 釋放節(jié)點內存（這里不寫也可以，但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; 
    } 
}; 

普通二叉樹的刪除方式

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

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

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

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

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

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); // 這里第一次操作目標值：交換目標值其右子樹最左面節(jié)點。 
        } 
        root->left = deleteNode(root->left, key); 
        root->right = deleteNode(root->right, key); 
        return root; 
    } 
}; 

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

迭代法

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

代碼如下：

class Solution { 
private: 
    // 將目標節(jié)點（刪除節(jié)點）的左子樹放到 目標節(jié)點的右子樹的最左面節(jié)點的左孩子位置上 
    // 并返回目標節(jié)點右孩子為新的根節(jié)點 
    // 是動畫里模擬的過程 
    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的父節(jié)點，用來刪除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; 
    } 
}; 

總結

讀完本篇，大家會發(fā)現(xiàn)二叉搜索樹刪除節(jié)點比增加節(jié)點復雜的多。

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

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

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

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

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

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

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

其他語言版本

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  #第一種情況：沒找到刪除的節(jié)點，遍歷到空節(jié)點直接返回了 
        if root.val == key: 
            if not root.left and not root.right:  #第二種情況：左右孩子都為空（葉子節(jié)點），直接刪除節(jié)點， 返回NULL為根節(jié)點 
                del root 
                return None 
            if not root.left and root.right:  #第三種情況：其左孩子為空，右孩子不為空，刪除節(jié)點，右孩子補位 ，返回右孩子為根節(jié)點 
                tmp = root 
                root = root.right 
                del tmp 
                return root 
            if root.left and not root.right:  #第四種情況：其右孩子為空，左孩子不為空，刪除節(jié)點，左孩子補位，返回左孩子為根節(jié)點 
                tmp = root 
                root = root.left 
                del tmp 
                return root 
            else:  #第五種情況：左右孩子節(jié)點都不為空，則將刪除節(jié)點的左子樹放到刪除節(jié)點的右子樹的最左面節(jié)點的左孩子的位置 
                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 

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