代码随想录-67-450. 删除二叉搜索树中的节点

这篇具有很好参考价值的文章主要介绍了代码随想录-67-450. 删除二叉搜索树中的节点。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

我在刷卡哥的“代码随想录”,自己的总结笔记均会放在“算法刷题-代码随想录”该专栏下。
代码随想录此题链接

题目

代码随想录-67-450. 删除二叉搜索树中的节点
代码随想录-67-450. 删除二叉搜索树中的节点
代码随想录-67-450. 删除二叉搜索树中的节点

1.二叉搜索树特性递归找到要删除的节点

按照二叉搜索树特性递归。

2. 本题思路分析:

递归三部曲:文章来源地址https://www.toymoban.com/news/detail-411458.html

  1. 参数与返回值:
  • 参数:当前节点cur和需要删除节点的值val
  • 返回值:返回TreeNode类型对象
  1. 终止条件:当前节点为null,说明没找到了需要删除的节点,则null即可。
  2. 单层循环逻辑:
  • 如果当前节点的值大于需要删除节点的值,则递归时用左孩子代入,并且递归函数的返回值用当前节点的左孩子接收;
  • 如果当前节点的值小于需要删除节点的值,则递归时用右子树代入,并且递归函数的返回值用当前节点的右子树接收;
  • 返回当前节点的值等于需要删除节点的值,就要删除当前节点,删除节点还有4种情况。
      1. 该节点左右孩子均为null,说明此为叶子节点。直接返回null。(因为递归函数的返回值会有对应左右孩子接收,在java中的删除,相当于父节点对应的左(右)孩子指针从指向本节点到指向null,本节点就找不到了,相当于就被删除了)
      1. 该节点右孩子为空,则说明左孩子不为空(因为第一种情况已经包括了左右孩子均为空的情况),则直接返回左孩子。因为相当于当前节点的左孩子替代了当前节点。(递归函数就是当前节点的父节点的左(右)孩子(也就是当前节点本身)接收,递归函数的参数也是当前节点的父节点的左(右)孩子(也就是当前节点本身),返回当前节点的左孩子,则相当于让当前节点的父节点的左孩子(当前节点的指针)指向了当前节点的左孩子,用当前节点的左孩子替换了当前节点,就相当于把当前节点删除。)
      1. 该节点左孩子为空,则说明右孩子不为空(因为第一种情况已经包括了左右孩子均为空的情况),则直接返回右孩子。分析同第2个。
      1. 改节点左右孩子均不为null。这个稍复杂,就是按照二叉搜索树的性质,当前节点的左子树中的所有节点一定比当前节点右子树中最小的节点还要小。所以应该把左子树放到右子树中最左边的叶子节点的左孩子位置,并且用当前节点的右孩子替换当前节点

3. 算法实现

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null){
            return null;
        }
        if(root.val == key){
            if(root.left == null && root.right == null){
                return null;
            }
            else if(root.right == null){
                return root.left;
            }else if(root.left == null){
                return root.right;
            }else{
                TreeNode cur = root.right;
                while(cur.left != null){
                    cur = cur.left;
                }
                cur.left = root.left;
                return root.right;
            }
        }else if(root.val > key){
            root.left = deleteNode(root.left, key);
        }else if(root.val < key){
            root.right = deleteNode(root.right, key);
        }
        return root;
    }
}

4. 算法坑点

  1. 本题,当终止条件(cur==null)时,说明在该二叉搜索树上并没有找到了要删除节点,此时直接返回null即可。
  2. 当前节点大于要插入节点的值,表明此时在向左子树中寻找要删除的节点,当cur.left代入参数时,注意这里最精妙的地方是递归函数返回值用cur.left接收
if(cur.val > val){
    cur.left = insertIntoBST(cur.left,val);
} 
  1. 当要删除当前节点,并且情况为当前节点左右孩子均不为null时,按照二叉搜索树的性质,当前节点的左子树中的所有节点一定比当前节点右子树中最小的节点还要小。所以应该把左子树放到右子树中最左边的叶子节点的左孩子位置,并且用当前节点的右孩子替换当前节点。(这个比较难想到)
TreeNode cur = root.right;
while(cur.left != null){//用循环找到最左边的叶子结点
    cur = cur.left;
}
cur.left = root.left;//左子树放到右子树中最左边的叶子节点的左孩子位置
return root.right;//用当前节点的右孩子替换当前节点

到了这里,关于代码随想录-67-450. 删除二叉搜索树中的节点的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [C++随想录] 二叉搜索树

    二叉搜索树 相较于 普通的二叉树来说: 根节点的左子树的所有键值都 小于 根节点, 根节点的右子树的所有键值 大于 根节点 根节点的 左右子树 都是 二叉搜索树 中序遍历 是 升序的 ⇒ 二叉搜素树 又叫作 二叉排序树 子树 节点 查找 假如查找 key, 有如下 四种情况 : 如果 key

    2024年02月06日
    浏览(37)
  • [代码随想录]二叉树

    二叉树可以链式存储,也可以顺序存储。 那么链式存储方式就用指针, 顺序存储的方式就是用数组。 顾名思义就是顺序存储的元素在内存是连续分布的,而链式存储则是通过指针把分布在各个地址的节点串联一起。 链式存储如图: 链式存储是大家很熟悉的一种方式,那么

    2024年02月03日
    浏览(59)
  • 代码随想录笔记--二叉树篇

    目录 1--递归遍历 1-1--前序遍历 1-2--中序遍历 1-3--后序遍历 2--迭代遍历 2-1--前序遍历 2-2--后序遍历 2-3--中序遍历 3--二叉树的层序遍历 4--翻转二叉树 5--对称二叉树 6--二叉树最大深度 7--二叉树的最小深度 8--完全二叉树节点的数量 9--平衡二叉树 10--二叉树的所有路径 11--左叶子之

    2024年02月10日
    浏览(49)
  • 代码随想录 二叉树 Java(二)

    采用前序遍历的方式遍历该二叉树,然后统计该二叉树的节点个数 这种方式比较简单,但是没有利用题目中所给的完全二叉树这一信息 官方思路:二分查找+位运算 对于任意二叉树,都可以通过广度优先搜索或深度优先搜索计算节点个数,时间复杂度和空间复杂度都是O(n),

    2024年02月08日
    浏览(51)
  • 跟着《代码随想录刷题》(六)—— 二叉树

    LeetCode:114、二叉树的前序遍历 (1)递归法 (2)迭代法 (3)统一迭代格式 LeetCode:94、二叉树的中序遍历 (1)递归法 (2)迭代法 (3)统一迭代格式 LeetCode:145、二叉树的后序遍历 (1)递归法 (2)迭代法 (3)统一迭代格式 LeetCode:589、N叉树前序遍历 LeetCode:590、N叉

    2024年02月09日
    浏览(47)
  • 代码随想录二刷 |二叉树 | 二叉树的右视图

    199.二叉树的右视图 给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 示例 1: 输入: [1,2,3,null,5,null,4] 输出: [1,3,4] 示例 2: 输入: [1,null,3] 输出: [1,3] 示例 3: 输入: [] 输出: [] 提示: 二叉树的节点个数的范围是 [0,1

    2024年02月04日
    浏览(61)
  • 1月3日代码随想录反转二叉树

    给你一棵二叉树的根节点  root  ,翻转这棵二叉树,并返回其根节点。 示例 1: 示例 2: 示例 3: 提示: 树中节点数目范围在  [0, 100]  内 -100 = Node.val = 100 这道题用递归的思想就是将根节点的左右儿子交换,然后再对子节点进行递归操作,直到子节点均为空。 但是我感觉

    2024年02月03日
    浏览(47)
  • 代码随想录day13 | 226.翻转二叉树 101.对称二叉树

    使用前、后序反转最为方便。 为啥不推荐中序? 中序遍历,某些节点的左右孩子会翻转两次,某些节点左右孩子不会被反转。 101.对称二叉树 关键在于,看这个节点对应的左子树和右子树是否可以相互反转。 1、如何比较呢? 比较的是两个子树的里侧和外侧的元素是否相等

    2024年02月15日
    浏览(39)
  • 【Day22-慢就是快】代码随想录-二叉树-迭代遍历

    用迭代法实现二叉树的前后中序遍历。 递归的实现就是:每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中 ,然后递归返回的时候,从栈顶弹出上一次递归的各项参数,所以这就是递归为什么可以返回上一层位置的原因。 此时大家应该知道我们用栈

    2024年02月10日
    浏览(47)
  • 【代码随想录day21】二叉树的最近公共祖先

    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 这题的难点在于: 如何建

    2024年02月15日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包