450.删除二叉搜索树中的结点 (Medium)*
题目描述*
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
- 首先找到需要删除的节点；
- 如果找到了，删除它。
说明*
要求算法时间复杂度为 O(h)，h 为树的高度。
代码*
先搜索要删除的结点，无子结点返回，仅有一个子结点替代，左右都不为空时可以选择使用其前驱或后继结点替代。
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(root == nullptr) {
return root;
}
if(root->val < key) {
root->right = deleteNode(root->right, key);
return root;
}
if(root-> val > key) {
root->left = deleteNode(root->left, key);
return root;
}
if(root->left == nullptr) {
TreeNode *tmp = root->right;
delete root;
return tmp;
}
if(root->right == nullptr) {
TreeNode *tmp = root->left;
delete root;
return tmp;
}
// 使用前驱替代
// TreeNode *cur = root->left;
// while(cur->right != nullptr) {
// cur = cur->right;
// }
// root->left = deleteNode(root->left, key);
// 使用后继替代
TreeNode *cur = root->right;
while(cur->left != nullptr) {
cur = cur->left;
}
int tmp = root->val;
root->val = cur->val;
cur->val = tmp;
root->right = deleteNode(root->right, key);
return root;
}
};
最后更新: July 23, 2022