前言
记录 五十八【701.二叉搜索树中的插入操作】保证插的新节点在叶子节点的位置,如此实现递归。
那么【450.删除二叉搜索树中的节点】删除如何实现?还有简单的方法吗?
一、题目阅读
给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
一般来说,删除节点可分为两个步骤:
首先找到需要删除的节点;
如果找到了,删除它。
示例 1:
或者删除之后:
输入:root = [5,3,6,2,4,null,7], key = 3
输出:[5,4,6,2,null,null,7]
解释:给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7],
另一个正确答案是 [5,2,6,null,4,null,7]。
示例 2:
输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点
示例 3:
输入: root = [], key = 0
输出: []
提示:
节点数的范围 [0, 10^4].
-10^5 <= Node.val <= 10^5
节点值唯一
root 是合法的二叉搜索树
-10^5 <= key <= 10^5
进阶: 要求算法时间复杂度为 O(h),h 为树的高度。
二、尝试实现
思路
- 题干告诉说:先找到目标;然后操作删除。
- 找目标:因为是二叉搜索树,利用大小关系的指向,可以向左或向右。即可找到目标;
- 删除操作:本题删除的节点可能不是叶子节点,可能有左子树或右子树。所以,比添加复杂一点。**将删除节点的左子树缀到右子树的合适位置,并将右子树返回上一层,**这样可以保证仍是二叉搜索树。(比如示意一的第一个正确答案)
- 递归函数参数:TreeNode* 当前节点。int key要删除的目标;
- 递归函数返回值:TreeNode* 类型。
- 终止条件:
- 如果是空,说明在树中没有找到要删除的目标,向上返回nullptr。最后返回原树:示例2.
- 如果找到目标:将左子树缀到右子树的合适位置,并将右子树返回上一层。
- 如果删除节点没有右子树,直接返回左子树;
- 如果有右子树,将左子树实现添加操作:如记录 五十八【701.二叉搜索树中的插入操作】缀到右子树
- 中间逻辑:向左或向右找删除目标对象。
代码实现【递归】
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(!root) return nullptr;
if(root->val == key){
if(!root->right) {
TreeNode* left = root->left;
delete root;
return left;
}else if(root->right){
if(!root->left) return root->right;
TreeNode* temp =root->right;
TreeNode* temppre = nullptr;
while(temp){
temppre = temp;
if(temp->val > root->left->val){
temp = temp->left;
}else if(temp->val < root->left->val){
temp = temp->right;
}
}
if(temppre->val > root->left->val) temppre->left = root->left;
else temppre->right = root->left;
TreeNode* right = root->right;
delete root;
return right;
}
}
if(root->val > key){
root->left = deleteNode(root->left,key);
}else if(root->val < key){
root->right = deleteNode(root->right,key);
}
return root;
}
};
总结:上面代码在找到删除目标之后,处理左右子树用到记录 五十八【701.二叉搜索树中的插入操作】中的迭代法。
三、参考学习
学习内容
- 思路分析:分5种情况——
- 没找到要删的节点;
- 要删除的是叶子节点,左子树空,右子树空;
- 删除目标不是叶子节点,左子树不空,右子树空;可以让父节点直接指向左子树。
- 删除目标不是叶子节点,左子树空,右子树不空;可以让父节点直接指向右子树。
- 删除目标不是叶子节点,左子树不空,右子树不空;调整(复杂点)。让右子树继位,左子树放到右子树中。指明放到右子树的最左下角的位置。
- 总结:思路和二、中分析的一致。
- 代码实现,对比参考代码:
-
左右子树都不为空。指明放到右子树的最左下角的位置,不用当成添加操作。要简单些。
TreeNode* cur = root->right; // 找右子树最左面的节点 while(cur->left != nullptr) { cur = cur->left; } cur->left = root->left; // 把要删除的节点(root)左子树放在cur的左孩子的位置 TreeNode* tmp = root; // 把root节点保存一下,下面来删除 root = root->right; // 返回旧root的右孩子作为新root delete tmp; // 释放节点内存(这里不写也可以,但C++最好手动释放一下吧) return root;
- 介绍了普通二叉树的删除方式。思路:将要删除的节点换到一个叶子节点的位置。等遍历整个树,遇到这个叶子节点的位置,用空代替,就完成删除操作。参考给了:右子树的最左端,可能一次交换无法把删除目标换到叶子节点的位置,但是继续交换,总能换到,自然最右端也可以。
- 进一步思考普通二叉树的5中情况:
- 没有删除目标,遍历整个树之后,遇到空return nullptr。返回是原来的树;
- 删除目标是叶子节点,左空,右空。return nullptr,上一层直接指向左子树。
- 删除目标不是叶子节点,左不空,右空,可以直接返回左子树,上一层直接指向左子树。
- 删除目标不是叶子节点,左空,右不空,可以在右子树中找一个叶子节点返回。交换就是多步换到叶子节点。
- 删除目标不是叶子节点,左不空,右不空,同第四点。
- 普通二叉树的删除,代码实现【递归】:
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(!root) return nullptr;
if(root->val == key){//找到目标
if(!root->right) {//没有右子树。
TreeNode* left = root->left;
delete root;
return left;//这里向上返回才能删除目标。
}else if(root->right){
TreeNode* right = root->right;
while(right->left){//左子树存在,直到左子树不存在
right = right->left;
}
swap(root->val,right->val);
//这里没有return ,因为还没删掉目标。
}
}
root->left = deleteNode(root->left);
root->right = deleteNode(root->right);
return root;
}
};
总结
【450.删除二叉搜索树中的节点】和【删除普通二叉树的节点】
(欢迎指正,转载标明出处)