31 lines
951 B
C++
31 lines
951 B
C++
#include "s0450_delete_node_in_a_bst.hpp"
|
|
|
|
TreeNode* S0450::deleteNode(TreeNode* root, int key) {
|
|
// 如果根节点为空,则直接返回
|
|
if (root == nullptr) return nullptr;
|
|
// 如果 key 等于根节点的值,则删除根节点,并将左子树的最右侧节点提上来
|
|
if (root->val == key) {
|
|
// 左子树为空的情况
|
|
if (root->left == nullptr) {
|
|
return root->right;
|
|
} else { // 左子树不为空时
|
|
// 找到左子树的最右侧节点
|
|
TreeNode *cur = root->left;
|
|
while (cur->right) {
|
|
cur = cur->right;
|
|
}
|
|
// 把这个节点提上来,并删除左子树中的该节点
|
|
cur->left = deleteNode(root->left, cur->val);
|
|
cur->right = root->right;
|
|
// 返回
|
|
return cur;
|
|
}
|
|
} else if (key < root->val) {
|
|
root->left = deleteNode(root->left, key);
|
|
return root;
|
|
} else {
|
|
root->right = deleteNode(root->right, key);
|
|
return root;
|
|
}
|
|
}
|