問(wèn)題描述

給定一個(gè)二叉搜索樹(shù)的根節(jié)點(diǎn) root 和一個(gè)值 key，刪除二叉搜索樹(shù)中的 key 對(duì)應(yīng)的節(jié)點(diǎn)，并保證二叉搜索樹(shù)的性質(zhì)不變。返回二叉搜索樹(shù)（有可能被更新）的根節(jié)點(diǎn)的引用。
一般來(lái)說(shuō)，刪除節(jié)點(diǎn)可分為兩個(gè)步驟：

• 首先找到需要?jiǎng)h除的節(jié)點(diǎn)；
• 如果找到了，刪除它。

說(shuō)明： 要求算法時(shí)間復(fù)雜度為 O(h)，h 為樹(shù)的高度。

Example

root = [5,3,6,2,4,null,7]
key = 3

給定需要?jiǎng)h除的節(jié)點(diǎn)值是 3，所以我們首先找到 3 這個(gè)節(jié)點(diǎn)，然后刪除它。

一個(gè)正確的答案是 [5,4,6,2,null,null,7], 如下圖所示。

另一個(gè)正確答案是 [5,2,6,null,4,null,7], 如下圖所示。

image.png

題目鏈接：450. 刪除二叉搜索樹(shù)中的節(jié)點(diǎn) (難度：中等)

思路

從題目描述中可知，我們需要做的事情有兩個(gè)：找到節(jié)點(diǎn)和刪除節(jié)點(diǎn)。我們考慮刪除當(dāng)前節(jié)點(diǎn)的情況：

• 若當(dāng)前節(jié)點(diǎn)是葉節(jié)點(diǎn)，則直接刪除
• 若當(dāng)前節(jié)點(diǎn)的左右孩子中有一棵為空，則用另一個(gè)子樹(shù)代替當(dāng)前節(jié)點(diǎn)
• 若當(dāng)前節(jié)點(diǎn)的左右孩子均非空，我們統(tǒng)一將左子樹(shù)作為根節(jié)點(diǎn)，并將右子樹(shù)掛到左子樹(shù)的最右結(jié)點(diǎn)的右端

其中，第一種情況是第二種情況的特例

代碼

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root == NULL)
            return NULL;
        if(root->val == key){
            if(root->left && root->right){
                TreeNode* tmp = root->left;
                while(tmp->right){
                    tmp = tmp->right;
                }
                tmp->right = root->right;
                return root->left;
            }
            return root->right == NULL ? root->left : root->right;
        }else if(root->val < key){
            root->right = deleteNode(root->right, key);
        }else{
            root->left = deleteNode(root->left, key);
        }
        return root;
    }
};

執(zhí)行結(jié)果：64 ms，32.5 MB