本文共 3657 字，大约阅读时间需要 12 分钟。

仰望星空的人，不应该被嘲笑

题目描述

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；

示例:

root = [5,3,6,2,4,null,7]key = 3    5   / \  3   6 / \   \2   4   7给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。    5   / \  4   6 /     \2       7另一个正确答案是 [5,2,6,null,4,null,7]。    5   / \  2   6   \   \    4   7

来源：力扣（LeetCode）

解题思路

对于这道题，我们必须先了解一下二叉搜索树（BST）的性质，如下：

BST性质

• 中序遍历是升序
• left小于当前节点，right大于当前节点
• 左子树、右子树也要是BST

了解了性质之后，我们知道要查找对应 key 值，可以与根节点进行比较，如果小于根节点，直接去左子树找就好了，如果大于根节点，直接去右子树找就好了。

而对于刚好等于根节点的话，我拿着大佬的图解来看看几种情况：

第一种情况，如果删除节点仅有右孩子，直接指向右孩子

① 找到要删除节点左子树的最右边的节点，即前驱的最大值（由BST性质得到）替换当前 root 节点，然后删除这个前驱

② 找到要删除节点右子树的最左边的节点，即后继最小值（由BST性质得到）替换当前 root 节点，然后删除这个后继

参考 大佬图解

代码提供了两种解法，对于前两种情况处理是一样的，只是对于最后一种情况，可以删除前驱的最大值，或者删除后继的最小值。

删除前驱的最大值代码

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { *     this.val = (val===undefined ? 0 : val) *     this.left = (left===undefined ? null : left) *     this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @param {number} key * @return {TreeNode} */var deleteNode = function (root, key) {
       if (!root) return null;    // 判断值是否小于root，小于走左子树，大于走右子树    if (key < root.val) {
           root.left = deleteNode(root.left, key);    } else if (key > root.val) {
           root.right = deleteNode(root.right, key);    } else {
           // 1.如果删除节点没有左右子树，直接删除即可        if (!root.left && !root.right) {
               root = null;        // 2.如果删除节点仅有左孩子，直接指向左孩子        } else if (root.left && !root.right) {
               root = root.left;        // 3.如果删除节点仅有右孩子，直接指向右孩子        } else if (!root.left && root.right) {
               root = root.right;        } else {
               // 4.如果左右孩子都有，本代码采用方式是将前驱的最大值替换root的值            let last = root.left;            while (last.right) {
                   last = last.right;            }            root.val = last.val;            // 然后删除这个前驱最大值节点即可            root.left = deleteNode(root.left, last.val);        }    }    return root;};

删除后继的最小值代码

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { *     this.val = (val===undefined ? 0 : val) *     this.left = (left===undefined ? null : left) *     this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @param {number} key * @return {TreeNode} */var deleteNode = function (root, key) {
       if (!root) return null;    // 判断值是否小于root，小于走左子树，大于走右子树    if (key < root.val) {
           root.left = deleteNode(root.left, key);    } else if (key > root.val) {
           root.right = deleteNode(root.right, key);    } else {
           // 1.如果删除节点没有左右子树，直接删除即可        if (!root.left && !root.right) {
               root = null;        // 2.如果删除节点仅有左孩子，直接指向左孩子        } else if (root.left && !root.right) {
               root = root.left;        // 3.如果删除节点仅有右孩子，直接指向右孩子        } else if (!root.left && root.right) {
               root = root.right;        } else {
               // 4.如果左右孩子都有，本代码采用方式是将后继的最小值替换root的值            let last = root.right;            while (last.left) {
                   last = last.left;            }            root.val = last.val;            // 然后删除这个后继最小值节点即可            root.right = deleteNode(root.right, last.val);        }    }    return root;};

最后

文章产出不易，还望各位小伙伴们支持一波！

往期精选：

小伙伴们可以在Issues中提交自己的解题代码，🤝 欢迎Contributing，可打卡刷题，Give a ⭐️ if this project helped you!

，方便小伙伴阅读玩耍~

学如逆水行舟，不进则退

转载地址：https://chocolate.blog.csdn.net/article/details/108781484 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！