【LeetCode二元樹#17】在二元搜尋樹中插入或刪除某個值（涉及重構二元樹、連結串列基礎、以及記憶體漏失問題）

二元搜尋樹中的插入操作

力扣題目連結(opens new window)

給定二元搜尋樹（BST）的根節點和要插入樹中的值，將值插入二元搜尋樹。 返回插入後二元搜尋樹的根節點。 輸入資料保證，新值和原始二元搜尋樹中的任意節點值都不同。

注意，可能存在多種有效的插入方式，只要樹在插入後仍保持為二元搜尋樹即可。 你可以返回任意有效的結果。

單獨說一下左右不為空的情況

如果待刪除節點的左右子節點不為空，這時候就涉及到調整二元樹的結構

由於二元搜尋樹的性質，左子樹的值均小於根節點

那麼當前節點刪除後，左子樹的節點是不可能直接放到刪除節點的位置的

刪掉的節點需要由右子節點補位

而刪除節點的左子樹需要整顆接到刪除節點的右子樹的最左邊節點的左子節點處

這個規則看似很複雜，但其實想想也說得通，下面通過圖示具體說明

如圖所示，節點7為待刪除節點，其左右子節點均不為空

當刪除節點7後，根據二元搜尋樹的規則，我們只能將節點7的右子節點9用於補位

因為如果用節點5（也就是左子節點），那麼節點9不論接到其後的哪個節點，均不能滿足二元搜尋樹的定義

即以下兩種情況：

回到題目

因為在二元搜尋樹中，待刪除節點7一定小於其右子樹的所有節點值，且一定大於其左子樹的所有子節點值

所以，待刪除節點7左子樹的所有子節點值一定是小於當前待刪除節點7有子樹的所有子節點值的

因此，當節點9補位被刪掉的節點7後，節點7的左子樹（以節點5為根節點）需要整體接到節點8的位置（以當前圖示為例，即待刪除節點的右子樹的最左節點的左子樹，因為這裡為待刪除節點的右子樹中值最小的位置）

程式碼

遞迴法

還是遞迴三部曲

1、確定遞迴函數的引數和返回值

因為我們需要通過遞迴的回溯（即返回值）來新增移動或補位的節點，所以遞迴函數中是需要返回值的

（簡明理解：根節點root最初呼叫了遞迴，當遞迴的最後一層完成了操作，所有結果需要層層返回，最後返回到最初的根節點root處，即完成了對二元樹的修改）

那麼解題模板可以直接使用

class Solution {
public:
    //確定遞迴函數的引數和返回值
    TreeNode* deleteNode(TreeNode* root, int key) {

    }
};

2、確定終止條件

這裡的終止條件指的是「如果沒找到待刪除節點，那麼不能讓遞迴無限迴圈下去」

因此只需要寫出思路分析中的「樹中不存在待刪除節點」的情況

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        //確定終止條件
		if(root = NULL) return root;
    }
};

3、確定單層處理邏輯

單層處理邏輯對應著找到待刪除節點的四種情況

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        //確定終止條件
		if(root = NULL) return root;
        
        //確定單層處理邏輯
        //如果找到了待刪除值
        //沒有左右子節點
        
        if(root->val == key){
            if (root->left == nullptr && root->right == nullptr) {
                //直接刪除節點並記憶體釋放
                delete root;
                return nullptr;
            }
            //其左子樹節點為空，右子樹節點不為空，返回被刪除節點的右子樹（的根節點）
            // else if(root->left == nullptr) return root->right;
            //不能像上面那樣寫，因為還要刪root，得用一個臨時node接一下root->right
            else if(root->left == nullptr){
                //接一下root->right
                auto resNode = root->right;
                delete root;//刪root
                return resNode;
            }


            //其右子樹節點為空，左子樹節點不為空，返回被刪除節點的左子樹（的根節點）
            // else if(root->right == nullptr) return root->left;//同理
            else if(root->right == nullptr){
                auto resNode = root->left;
                delete root;
                return resNode;
            }
        }    
    }
};

接下來處理待刪除節點的左右子節點不為空的情況

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        //確定終止條件
		if(root == nullptr) return root;
        
        //確定單層處理邏輯
        //如果找到了待刪除值
        //沒有左右子節點
        
        if(root->val == key){
            if (root->left == nullptr && root->right == nullptr) {
                //直接刪除節點並記憶體釋放
                delete root;
                return nullptr;
            }
            //其左子樹節點為空，右子樹節點不為空，返回被刪除節點的右子樹（的根節點）
            // else if(root->left == nullptr) return root->right;
            //不能像上面那樣寫，因為還要刪root，得用一個臨時node接一下root->right
            else if(root->left == nullptr){
                //接一下root->right
                auto resNode = root->right;
                delete root;//刪root
                return resNode;
            }
            //其右子樹節點為空，左子樹節點不為空，返回被刪除節點的左子樹（的根節點）
            // else if(root->right == nullptr) return root->left;//同理
            else if(root->right == nullptr){
                auto resNode = root->left;
                delete root;
                return resNode;
            }
            else{//待刪除節點的左右子節點不為空
                //先去遍歷待刪除節點的右子樹的左分支，找到最左邊的節點
                //定義一個指標
                TreeNode* cur = root->right;
                while(cur->left != nullptr){//遍歷右子樹的左分支
                    cur = cur->left;
                }//迴圈結束就找到了最左節點
                //刪除root節點並移動其左子樹
                //把要刪除的節點（root）左子樹放在cur的左子節點的位置
                cur->left = root->left;
                //儲存一下當前的root節點，待會要把它指向其右子節點
                TreeNode* temp = root;//保證刪除root時刪的是root，而不是修改後的root->right
                //root被其右子節點補位
                root = root->right;
                //刪除temp、root
                delete temp;
                return root;  
            }
        }
        //還沒找到待刪除值就繼續呼叫遞回去找
        if(root->val > key){
            root->left = deleteNode(root->left, key);//相當於把之後調整的新節點返回回來，並用left接收
            //如果目標值在左子樹被發現，那麼左子樹結構肯定變化，因此需要返回新的節點
        }else if(root->val < key){
            root->right = deleteNode(root->right, key);//同理
        } 
        return root;   
    }
};

迭代法

TBD

天坑

本題的思路過得差不多了

但在coding時遇到了很多問題

1、刪除一個節點的正確方法

先使用一個臨時節點把待刪除節點儲存，然後讓該節點指向你規定的下一個節點（連結串列基礎遺忘）

//其左子樹節點為空，右子樹節點不為空，返回被刪除節點的右子樹（的根節點）
            // else if(root->left == nullptr) return root->right;
            //不能像上面那樣寫，因為還要刪root，得用一個臨時node接一下root->right
            else if(root->left == nullptr){
                //接一下root->right
                auto resNode = root->right;
                delete root;//刪root
                return resNode;
            }

2、NULL和nullptr的區別

參考

在C++中，NULL為整數0；nullptr代表空指標

3、記憶體漏失

記憶體漏失比較難以定位，通常報錯如下：

-----=-42==ERROR: AddressSanitizer: heap-use-after-free on address 0x60300000100 at pc 0x0000034fc9 bp 0x7fff5d8c78d0 sp 0x7ff5d8c78c8READ of size 4 at 0x603000000100 thread TO
#3 0x7faf469e4082 (/lib/x86_64-linux-gnu/libc.so.6+0x24082)0x603000000100 is ocated 0 bytes inside of 24-byte region [0x603000000100,0x603000000118)freed by thread To here:
#4 0x7faf469e4082 (/lib/x86_64-linux-gnu/libc.so.6+0x24082)previously allocated by thread To here:
#4 0x7faf469e4082 (/lib/x86_64-linux-gnu/libc.so.6+0x24082)Shadow bytes around the buggy address :
0x0c067fff7fdo: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c067fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 0 00 00 00 000x0c067fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

這是一個AddressSanitizer檢測到的錯誤，指出在程式執行時使用了一個已經釋放的記憶體地址

一般來說，是某處使用指標沒有釋放，或者對指標進行了不正確的操作導致的

可以照著這個思路排除所有使用指標的地方
（做這題的時候™的就是return寫成delete了，即錯誤操作了某個指標導致報錯）