本站消息

站长简介/公众号


关注本站官方公众号:程序员总部,领取三大福利! 福利一:python和前端辅导 福利二:进程序员交流微信群,专属于程序员的圈子 福利三:领取全套零基础视频教程(python,java,前端,php)

  价值13000svip视频教程,java大神匠心打造,零基础java开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长


+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2021-08(22)

2021-09(40)

2021-10(44)

2021-11(50)

2021-12(65)

Java描述 LeetCode,450. Delete Node in a BST 删除二叉树中的某一个值

发布于2022-01-06 08:18     阅读(1123)     评论(0)     点赞(10)     收藏(4)


大家好,我是河海哥,专注于后端,如果可以的话,想做一名code designer而不是普通的coder,一起见证河海哥的成长,您的评论与赞与关注是我的最大动力,如有错误还请不吝赐教,万分感谢。一起支持原创吧!纯手打有笔误还望谅解。

1-1:题目描述

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.
If the node is found, delete the node.

Example 1:
在这里插入图片描述

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.

Example 3:

Input: root = [], key = 0
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 104].
-105 <= Node.val <= 105
Each node has a unique value.
root is a valid binary search tree.
-105 <= key <= 105

Follow up: Could you solve it with time complexity O(height of tree)?

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

1-2:递归解法

☘️首先,先把流程搞清楚,删除二叉树上的节点大概有这几种情况

  • 删除的刚好是叶子节点
  • 删除的是非叶子节点
    • 删除的节点有左孩子无右孩子;做法:找到左孩子的最右侧节点,也就是二叉搜索树中序遍历的前驱节点。然后把这个节点和被删除的节点互换。
    • 删除的节点无左孩子有右孩子;做法:找到右孩子的最左侧节点,也就是二叉搜索树中序遍历的后继节点。然后把这个节点和被删除的节点互换。
    • 删除的节点有左孩子也有右孩子;做法,找到左孩子的最右侧节点或者找到右孩子的最左侧节点,然后进行互换操作。

☘️知道了整个流程,让我们来写代码。首先先写,如何找到左孩子的最右侧节点,找到右孩子的最左侧节点。

public TreeNode findLeftRightest(TreeNode root) {
    root = root.left;
    while (root.right != null) {
        root = root.right;
    }
    return root;
}

public TreeNode findRightLeftest(TreeNode root) {
    root = root.right;
    while (root.left != null) {
        root = root.left;
    }
    return root;
}

☘️接着如果你做过Java描述 LeetCode,701. Insert into a Binary Search Tree 在二叉搜索树中插入一个值,这道题,就可以把框架先打起来了。

if (root == null) {
    return null;
}
if (key < root.val) {
    root.left = deleteNode(root.left, key);
}
if (key > root.val) {
    root.right = deleteNode(root.right, key);
}
if (key == root.val) {

}
return root;

☘️关键就是命中的时候,由上面的701题可以知道,我们函数返回的都是重新构建之后的那个节点,所以根据上面的几种情况我们来看。

  • 删除的刚好是叶子节点。
    那么,叶子节点直接删除就好了,也就是这个root节点直接变成null,返回的null就是重新构建之后的那个节点,原来的节点变成了null。
    if (root.left == null && root.right == null) {
        return null;
    }
    
  • 删除的不是叶子节点
    • 删除的节点有左孩子无右孩子;
      if (root.left != null && root.right == null) {
          TreeNode leftRightest = findLeftRightest(root);
          root.val = leftRightest.val;
          root.left = deleteNode(root.left, leftRightest.val);
      }
      
      首先找到最左侧的最右节点leftRightest,之后,将root的值替换成它,之后想办法把leftRightest这个节点删除不就OK了?所以继续递归,进行删除。
    • 删除的节点无左孩子有右孩子;删除的节点有左孩子也有右孩子;同样的道理,这两个可以合并成一种情况,用一种逻辑。
      if ((root.right != null && root.left == null)
              || (root.right != null && root.left != null)) {
          TreeNode rightLeftest = findRightLeftest(root);
          root.val = rightLeftest.val;
          root.right = deleteNode(root.right, rightLeftest.val);
      }
      

☘️最终的代码如下:

public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) {
        return null;
    }
    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    }
    if (key > root.val) {
        root.right = deleteNode(root.right, key);
    }
    if (key == root.val) {
        if (root.left == null && root.right == null) {
            return null;
        }
        if (root.left != null && root.right == null) {
            TreeNode leftRightest = findLeftRightest(root);
            root.val = leftRightest.val;
            root.left = deleteNode(root.left, leftRightest.val);
        }
        if ((root.right != null && root.left == null)
                || (root.right != null && root.left != null)) {
            TreeNode rightLeftest = findRightLeftest(root);
            root.val = rightLeftest.val;
            root.right = deleteNode(root.right, rightLeftest.val);
        }
    }
    return root;
}

public TreeNode findLeftRightest(TreeNode root) {
    root = root.left;
    while (root.right != null) {
        root = root.right;
    }
    return root;
}

public TreeNode findRightLeftest(TreeNode root) {
    root = root.right;
    while (root.left != null) {
        root = root.left;
    }
    return root;
}

1-3:总结

主要就是把二叉搜索树的删除操作再复习了一遍。
在这里插入图片描述

原文链接:https://blog.csdn.net/qq_41376740/article/details/122318702

关注本站官方公众号:程序员总部,领取三大福利! 福利一:python和前端辅导 福利二:进程序员交流微信群,专属于程序员的圈子 福利三:领取全套零基础视频教程(python,java,前端,php)
欢迎关注我的公众号:程序员总部,关注公众号回复java,免费领取 全套java视频教程,关注公众号回复java充值+你的账号,免费为您充值1000积分



所属网站分类: 技术文章 > 博客

作者:程序员之神

链接:http://www.javaheidong.com/blog/article/372902/b27e9c9f4650fbaccbd3/

来源:java黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

10 0
收藏该文
已收藏

评论内容:(最多支持255个字符)