算法力扣刷题记录 五十九【450.删除二叉搜索树中的节点】

avatar
作者
猴君
阅读量:0

前言

记录 五十八【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 为树的高度。


二、尝试实现

思路

  1. 题干告诉说:先找到目标;然后操作删除。
  2. 找目标:因为是二叉搜索树,利用大小关系的指向,可以向左或向右。即可找到目标;
  3. 删除操作:本题删除的节点可能不是叶子节点,可能有左子树或右子树。所以,比添加复杂一点。**将删除节点的左子树缀到右子树的合适位置,并将右子树返回上一层,**这样可以保证仍是二叉搜索树。(比如示意一的第一个正确答案)
  4. 递归函数参数:TreeNode* 当前节点。int key要删除的目标;
  5. 递归函数返回值:TreeNode* 类型。
  6. 终止条件:
  • 如果是空,说明在树中没有找到要删除的目标,向上返回nullptr。最后返回原树:示例2.
  • 如果找到目标:将左子树缀到右子树的合适位置,并将右子树返回上一层。
  1. 中间逻辑:向左或向右找删除目标对象。

代码实现【递归】

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.二叉搜索树中的插入操作】中的迭代法


三、参考学习

参考学习链接

学习内容

  1. 思路分析:分5种情况——
  • 没找到要删的节点;
  • 要删除的是叶子节点,左子树空,右子树空;
  • 删除目标不是叶子节点,左子树不空,右子树空;可以让父节点直接指向左子树。
  • 删除目标不是叶子节点,左子树空,右子树不空;可以让父节点直接指向右子树。
  • 删除目标不是叶子节点,左子树不空,右子树不空;调整(复杂点)。让右子树继位,左子树放到右子树中。指明放到右子树的最左下角的位置
  • 总结思路和二、中分析的一致。
  1. 代码实现,对比参考代码:
  • 左右子树都不为空。指明放到右子树的最左下角的位置,不用当成添加操作。要简单些。

    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; 
  1. 介绍了普通二叉树的删除方式。思路将要删除的节点换到一个叶子节点的位置。等遍历整个树,遇到这个叶子节点的位置,用空代替,就完成删除操作。参考给了:右子树的最左端,可能一次交换无法把删除目标换到叶子节点的位置,但是继续交换,总能换到,自然最右端也可以。
  2. 进一步思考普通二叉树的5中情况
  • 没有删除目标,遍历整个树之后,遇到空return nullptr。返回是原来的树;
  • 删除目标是叶子节点,左空,右空。return nullptr,上一层直接指向左子树。
  • 删除目标不是叶子节点,左不空,右空,可以直接返回左子树,上一层直接指向左子树。
  • 删除目标不是叶子节点,左空,右不空,可以在右子树中找一个叶子节点返回。交换就是多步换到叶子节点。
  • 删除目标不是叶子节点,左不空,右不空,同第四点。
    在这里插入图片描述
  1. 普通二叉树的删除,代码实现【递归】:
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.删除二叉搜索树中的节点】和【删除普通二叉树的节点】

在这里插入图片描述
(欢迎指正,转载标明出处)

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!