首页 > 编程语言 >算法力扣刷题记录 五十九【450.删除二叉搜索树中的节点】

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

时间:2024-07-25 12:55:02浏览次数:15  
标签:right 删除 450 root 右子 力扣 树中 节点 left

前言

记录 五十八【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.删除二叉搜索树中的节点】和【删除普通二叉树的节点】

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

标签:right,删除,450,root,右子,力扣,树中,节点,left
From: https://blog.csdn.net/danaaaa/article/details/140682549

相关文章

  • 算法力扣刷题记录 五十七【236. 二叉树的最近公共祖先】和【235. 二叉搜索树的最近公
    前言公共祖先解决。二叉树和二叉搜索树条件下的最近公共祖先。二叉树篇继续。一、【236.二叉树的最近公共祖先】题目阅读给定一个二叉树,找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树T的两个节点p、q,最近公共祖先表示为一......
  • 力扣-图
    目录图200-岛屿数量-中等130-被围绕的区域-中等133-克隆图-中等399-除法求值-中等-反复看207-课程表-中等210-课程表II-中等909-蛇梯棋-中等-变态433-最小基因变化-中等-BT127-单词接龙-中等208-实现Trie(前缀树)-中等212-单词搜索-困难211-添加与搜索单词-数据结构涉及-中等BFS......
  • 力扣1456. 定长子串中元音的最大数目(java)
     题目描述示例思路看到“定长子串”时,我们容易联想到用滑动数组来实现这个算法。滑动数组允许我们在每次移动窗口时,只需增加新元素并减去旧元素的计数,而不必重新计算整个窗口的内容,相对于其他复杂的算法来说,实现起来更为直观和简单解题方法1.首先创建isVomel方法......
  • 力扣高频SQL 50题(基础版)第九题
    文章目录力扣高频SQL50题(基础版)第九题197.上升的温度题目说明思路分析实现过程准备数据实现方式结果截图总结力扣高频SQL50题(基础版)第九题197.上升的温度题目说明Weather±--------------±--------+|ColumnName|Type|±--------------±--------+......
  • 力扣高频SQL 50题(基础版)第八题
    文章目录力扣高频SQL50题(基础版)第八题1581.进店却未进行过交易的顾客题目说明思路分析实现过程准备数据:实现方式:结果截图:总结:力扣高频SQL50题(基础版)第八题1581.进店却未进行过交易的顾客题目说明表:Visits±------------±--------+|ColumnName|Type|......
  • 24暑假算法刷题 | Day20 | LeetCode 235. 二叉搜索树的最近公共祖先,701. 二叉搜索树中
    目录235.二叉搜索树的最近公共祖先题目描述题解701.二叉搜索树中的插入操作题目描述题解450.删除二叉搜索树中的节点题目描述题解235.二叉搜索树的最近公共祖先点此跳转题目链接题目描述给定一个二叉搜索树,找到该树中两个指定节点的最近公共祖先。百度......
  • 题解:P10450 [USACO03MAR] Best Cow Fences G
    题目链接O(n^3)做法直接暴力枚举长度、起点,再全部跑一边求平均数。附上我丑陋的代码和提交记录,这个代码可以得42分。#include<bits/stdc++.h>usingnamespacestd;constintNR=1e5+5;longlongn,l,a[NR],sum,ave;intmain(){ cin>>n>>l; for(inti......
  • 【算法专题】双指针算法之611. 有效三角形的个数(力扣)
    欢迎来到CILMY23的博客......
  • 【算法专题】双指针算法之LCR 179. 查找总价格为目标值的两个商品(力扣)
     欢迎来到CILMY23的博客......
  • 代码随想录算法训练营第20天 | 二叉搜索树中级
    2024年7月22日题235.二叉搜索树的最近公共祖先普通解法还是和普通的祖先一样求即可,再依据搜索树特性进行剪枝即可加速。importjava.util.*;classSolution{Vector<TreeNode>vec1;Vector<TreeNode>vec2;intflag1=0;intflag2=0;publicT......