【算法题解】62. 删除二叉搜索树中的节点

❝

这是一道 「中等难度」 的题
https://leetcode.cn/problems/delete-node-in-a-bst/

❞

题目

给定一个二叉搜索树的根节点 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 
输出: []

提示:

节点数的范围
节点值唯一
是合法的二叉搜索树

什么是二叉树搜索树

解题之前需要先了解一下什么是 「二叉搜索树」。

二叉搜索树首先肯定得先是一颗二叉树，然后在此基础上呢还需要满足以下几点要求：

左子树的节点都要 「小于等于」 根节点。
右子树的节点都要 「大于等于」 根节点。
所有子树也都同样需要满足上面两点，也就是说二叉搜索树的任意子树同样也还是二叉搜索树。

如下图所示：从图中可以很容易的看出：「二叉搜索树的中序遍历必然是一个有序序列」。如上图中二叉搜索树的中序遍历为。

根据上述定义我们也可以很清楚的知道它为啥叫二叉搜索树了。当我们使用二叉搜索树来检索一个值的时候，「只要不断的和当前根节点的值比较即可」，就可以立即排除掉一半的节点，效率非常高。普通二叉树是做不到这一点的，必须一个一个节点的去找，不管是深度优先还是广度优先。

题解

解题思路主要分两步：

找到待删除节点。
删除找到的节点。

如何找到待删除节点？

找到需要删除的节点比较简单，就是根据二叉搜索树的特性，用给定的 key 不断的和根节点 root 进行对比：

key > root.val：就往右子树继续找。
key < root.val：就往左子树继续找。
key == root.val：找到了，当前节点 root 就是待删除的节点。

删除找到的节点

根据二叉搜索树的特性：

如果待删除节点没有右子树：说明待删除节点的值是整棵树中的最大值，其没有后继者，直接删除即可。
如果待删除节点包含右子树：说明待删除节点有后继者，将待删除节点的值设置为其后继者的值，然后将其右子树中的后继者删除。

Java 代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null){
            return null;
        }

        if(key == root.val){
            // 找后继
            if(root.right == null){
                return root.left;
            }else{
                TreeNode next = root.right;
                while(next.left != null){
                    next = next.left;
                }
                root.val = next.val;
                root.right = deleteNode(root.right, next.val);
            }

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

        return root;
    }

}

Go 代码实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }

    if key == root.Val {
        // 找后继
        if root.Right == nil {
            return root.Left
        }else {
            next := root.Right
            for next.Left != nil {
                next = next.Left
            }

            root.Val = next.Val

            // 删除next
            root.Right = deleteNode(root.Right, next.Val)
        }

    }else if key > root.Val {
        root.Right = deleteNode(root.Right, key)
    }else {
        root.Left = deleteNode(root.Left, key)
    }

    return root
}