首页 > 编程语言 >leetcode 450. Delete Node in a BST 删除二叉搜索树中的节点 (中等)

leetcode 450. Delete Node in a BST 删除二叉搜索树中的节点 (中等)

时间:2022-10-21 19:37:34浏览次数:92  
标签:Node 删除 450 二叉 BST key null root 节点

一、题目大意

给定一个二叉搜索树的根节点 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, 104].

  • -105 <= Node.val <= 105

  • 节点值唯一

  • root 是合法的二叉搜索树

  • -105 <= key <= 105

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/delete-node-in-a-bst
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、解题思路

这道题让我们删除二叉搜索树中的一个节点,难点在于删除完节点并补上那个节点的位置后还应该是一棵二叉搜索树。被删除掉的节点位置,不一定是由其左右节点补上,

         7
        / \
       4   8
     /   \   
    2     6
     \   /
      3 5

上面这棵树,如果要删除节点4,那么应该将节点5补到4的位置,这样才能保证还是BST,结果是下面这棵树

         7
        / \
       5   8
     /   \   
    2     6
     \   
      3

递归思路:首先判断根节点是否为空,由于BST的性质:左 < 根 < 右,使得可以快速定位到要删除的节点,对于当前节点值不等于key的情况,根据大小关系对其左右子节点分别调用递归函数。若当前节点就是要删除的节点,先判断若有一个子节点不存在,就将root指向另一个节点,如果左右节点都不存在,那么root就赋值为空了,也正确。难点就在于处理左右子节点都存在的情况,需要在右子树找到最濉址,即右子树中最左下方的节点,然后将该最小值赋值给root,然后再在右子树中调用递归函数来mbmw这个最小的节点。

三、解题方法

3.1 Java实现

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

四、总结小记

  • 2022/10/21 脑力劳动的人更容易摸鱼

标签:Node,删除,450,二叉,BST,key,null,root,节点
From: https://www.cnblogs.com/okokabcd/p/16814554.html

相关文章

  • 使用n管理node
    安装ncurl-Lhttp://git.io/n-install|bash安装完记得source一下安装node[1]安装指定版本n6.4.0[2]安装最新版本nlatest[3]安装稳定版本nstable切换版本......
  • NodeJS & Dapr Javascript SDK 官方使用指南
    Dapr是一个可移植的、事件驱动的运行时,它使任何开发人员能够轻松构建出弹性的、无状态和有状态的应用程序,并可运行在云平台或边缘计算中,它同时也支持多种编程语言和开发框......
  • 当通过docker node ls查询集群节点状态,一个节点状态是unreachable,这究竟代表什么意思?
    当通过dockernodels命令查询集群中各个节点的状态时: 在"MANAGERSTATUS"列出现“Unreachable”,这个代表的是什么意思?[root@nccztsjb-node-05~]#dockernodelsID......
  • 深入nodejs的event-loop
    此处如无特殊指出的话,eventloop的语境都是指nodejs本文研究所用的nodejs环境是:操作系统window10+nodejs版本号为v12.16.2什么是eventloop?eventloop是指由libuv......
  • 细说nodejs的path模块
    前言path模块是nodejs中用于处理文件/目录路径的一个内置模块,可以看作是一个工具箱,提供诸多方法供我们使用,当然都是和路径处理有关的。同时在前端开发中path模块出现......
  • 修改node安装路径后修改对应环境变量的详细操作
    一、修改node_global路径和node_cache路径在node安装路径下创建node_global和node_cache文件夹按win+R键打开运行窗口,输入cmd打开命令行,在命令行里面输入以下信息修......
  • node的更新最新版本
    node的下载地址:node官网1、下载的安装包点击安装,在安装过程中安装路径可以自己选择,其他的不用修改一直点击‘next’就可以2、打开cmd输入node-v;出现版本号即安装成功2.......
  • JavaScript字符串一些方法使用charAt、charCodeAt、replace、split、substr
    charAt():根据下标返回字符1<script>2letstr='abcde';3console.log(str.charAt(1));//返回结果:b4</script> charCodeAt():根据下标返回字......
  • Oracle substr用法
    一、正序截取字符substr(字符串,起始位置,截取长度)二、倒叙截取字符substr(字符串,截取长度)举例:substr('hello',-3)从o开始截取,共截取三位,结果为'llo'......
  • 6、SpriteKit 之 SKCameraNode
    SKCameraNode当场景的尺寸需要超过屏幕,需要移动或者缩放去查看更多界面时,就可以是使用SKCameraNode。在SKScene中使用。SKScene中的camera属性默认是nil。需要自......