一、题目大意

给定一个二叉搜索树的根节点 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 脑力劳动的人更容易摸鱼

原文地址:http://www.cnblogs.com/okokabcd/p/16814554.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性