問(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
