Java描述 LeetCode，450. Delete Node in a BST 删除二叉树中的某一个值-java黑洞网

本站消息

站长简介/公众号

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

程序员之神

565

文章

259654

访问

+关注

分类

暂无分类

日期归档

2023-06(3)

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

发布于2022-01-06 08:18 阅读(1306) 评论(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;
}