[LeetCode] 450. Delete Node in a BST 删除二叉搜索树中的节点

2021年09月15日 阅读数：1

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.html

Basically, the deletion can be divided into two stages:java

1. Search for a node to remove.
2. If the node is found, delete the node.

Note: Time complexity should be O(height of tree).node

Example:python

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

5
/ \
3   6
/ \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

5
/ \
4   6
/     \
2       7

5
/ \
2   6
\   \
4   7```

Java:url

```public TreeNode deleteNode(TreeNode root, int key) {
if(root == null){
return null;
}
if(key < root.val){
root.left = deleteNode(root.left, key);
}else if(key > root.val){
root.right = deleteNode(root.right, key);
}else{
if(root.left == null){
return root.right;
}else if(root.right == null){
return root.left;
}

TreeNode minNode = findMin(root.right);
root.val = minNode.val;
root.right = deleteNode(root.right, root.val);
}
return root;
}

private TreeNode findMin(TreeNode node){
while(node.left != null){
node = node.left;
}
return node;
}
```

Java: Iterativehtm

```    private TreeNode deleteRootNode(TreeNode root) {
if (root == null) {
return null;
}
if (root.left == null) {
return root.right;
}
if (root.right == null) {
return root.left;
}
TreeNode next = root.right;
TreeNode pre = null;
for(; next.left != null; pre = next, next = next.left);
next.left = root.left;
if(root.right != next) {
pre.left = next.right;
next.right = root.right;
}
return next;
}

public TreeNode deleteNode(TreeNode root, int key) {
TreeNode cur = root;
TreeNode pre = null;
while(cur != null && cur.val != key) {
pre = cur;
if (key < cur.val) {
cur = cur.left;
} else if (key > cur.val) {
cur = cur.right;
}
}
if (pre == null) {
return deleteRootNode(cur);
}
if (pre.left == cur) {
pre.left = deleteRootNode(cur);
} else {
pre.right = deleteRootNode(cur);
}
return root;
}　　```

Python:blog

```# Time:  O(h)
# Space: O(h)

class Solution(object):
def deleteNode(self, root, key):
"""
:type root: TreeNode
:type key: int
:rtype: TreeNode
"""
if not root:
return root

if root.val > key:
root.left = self.deleteNode(root.left, key)
elif root.val < key:
root.right = self.deleteNode(root.right, key)
else:
if not root.left:
right = root.right
del root
return right
elif not root.right:
left = root.left
del root
return left
else:
successor = root.right
while successor.left:
successor = successor.left

root.val = successor.val
root.right = self.deleteNode(root.right, successor.val)

return root
```

Python:

```def deleteNode(root, key):
if not root: # if root doesn't exist, just return it
return root
if root.val > key: # if key value is less than root value, find the node in the left subtree
root.left = deleteNode(root.left, key)
elif root.val < key: # if key value is greater than root value, find the node in right subtree
root.right= deleteNode(root.right, key)
else: #if we found the node (root.value == key), start to delete it
if not root.right: # if it doesn't have right children, we delete the node then new root would be root.left
return root.left
if not root.left: # if it has no left children, we delete the node then new root would be root.right
return root.right
# if the node have both left and right children,  we replace its value with the minmimum value in the right subtree and then delete that minimum node in the right subtree
temp = root.right
mini = temp.val
while temp.left:
temp = temp.left
mini = temp.val
root.val = mini # replace value
root.right = deleteNode(root.right,root.val) # delete the minimum node in right subtree
return root　```

C++:

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

C++:

```class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
TreeNode *cur = root, *pre = NULL;
while (cur) {
if (cur->val == key) break;
pre = cur;
if (cur->val > key) cur = cur->left;
else cur = cur->right;
}
if (!cur) return root;
if (!pre) return del(cur);
if (pre->left && pre->left->val == key) pre->left = del(cur);
else pre->right = del(cur);
return root;
}
TreeNode* del(TreeNode* node) {
if (!node->left && !node->right) return NULL;
if (!node->left || !node->right) {
return (node->left) ? node->left : node->right;
}
TreeNode *pre = node, *cur = node->right;
while (cur->left) {
pre = cur;
cur = cur->left;
}
node->val = cur->val;
(pre == node ? node->right : pre->left) = cur->right;
return node;
}
};　```

C++:

```// Time:  O(h)
// Space: O(h)

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) {
return nullptr;
}
if (root->val > key) {
root->left = deleteNode(root->left, key);
} else if (root->val < key) {
root->right = deleteNode(root->right, key);
} else {
if (!root->left) {
auto right = root->right;
delete root;
return right;
} else if (!root->right) {
auto left = root->left;
delete root;
return left;
} else {
auto successor = root->right;
while (successor->left) {
successor = successor->left;
}
root->val = successor->val;
root->right = deleteNode(root->right, successor->val);
}
}
return root;
}
};
```