【刷题日记】450. 删除二叉搜索树中的节点

本次刷题日记的第 53 篇，力扣题为：450. 删除二叉搜索树中的节点，中等

一、题目描述：

又是一个二叉树的题目，不过这题比之前的二叉树还有点不一样，有点意思，可以练习分类的思维

二、这道题考察了什么思想？你的思路是什么？

一起来看看这个题目主要表达了哪些诉求

• 题目中给出一个数组，表示的是一颗二叉搜索树，具体数据展示顺序是二叉树层序遍历的结果
• 题目要求我们，删除二叉树中指定的一个数字，并且返回 root，应该是一颗新的树

根据题目的要求，我们用脑袋思考一下，很明显，删除一个节点，咱们的二叉树有一定概率是需要被调整的，那么调整的规则又是啥样的呢？

这里就需要明白什么是二叉搜索树了，简单的来说就是二叉树中，

• 左节点数字一定是小于当前节点的数字，右节点的数字一定是大于当前节点的数字
• 左子树所有的数字都是小于右子树的

正如这样

可以看到，无论哪一个节点，左子树的值永远全部小于右子树的值

并且，我们就可以看出来，

• 如果想找到当前节点的最小值，那么就可以一直找这个树的左节点，直到没有左节点的时候，找到的这个节点就是整棵树中的最小值
• 同理，想要找这棵树的最大值，那么就找树的右节点即可

那么对于这道题，咱们要删除二叉搜索树中的某一个树，我们需要如何去思考呢？

删除二叉树的某一个节点，那么这一个节点存在的位置就很考究了，大致就会有这几种情况

• 树是空的，我们没办法删除
• 需要删除的数字就是整棵树的 根节点
• 需要删除的数字小于当前的根节点，那么我们就可以在左子树中去找
• 需要删除的数字大于当前的根节点，那么我们就可以去右子树中找
• 需要删除的数字是叶子节点，即，没有左子树，也没有右子树，或者其中一个子树为空
• 若删除的数字是当前节点，且左子树和右子树都有，那么我们如何考虑呢？

例如上图中，我们需要删除数字为 5 的节点，我们应该怎么呢？如下图

• 我们可以先找到 5 这个节点的左子树中的最大的数字 3
• 然后将 5 的右子树调整到 3 的右子树上
• 最后返回 5 的左子树 2
• 那么最终就可以得到如下图的一棵树了

这么看来，这道题的解法就相当明确了，那就是使用递归的方式，去找到需要删除的节点，根据节点的所处情况，来进行不同类型的处理即可，最终得到的结果还是一个二叉搜索树

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

这里需要注意，找到删除的节点之后，要根据当前节点是否有左子树，来进行分类处理

编码如下：

/**
 * 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 root.Val > key {
        root.Left = deleteNode(root.Left, key)
    }else if root.Val < key {
        root.Right =  deleteNode(root.Right, key)
    }else if root.Left == nil || root.Right == nil {
        if root.Left == nil {
            return root.Right
        }
        return root.Left
    }else {
        // root 节点的左子树和右子树都不为空的时候
        // 咱们找到 root 左子树的数字最大的一个节点
        cur := root.Left
        for cur.Right != nil {
            cur = cur.Right
        }
        cur.Right = root.Right
        return root.Left
    }
    return root
}

四、总结：

这么看来，时间复杂度是 O(n) ，咱们遍历一遍左子树或者是右子树，空间复杂度也是 O(n) ，咱们使用递归，占用了栈空间

原题地址：450. 删除二叉搜索树中的节点

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是小魔童哪吒，欢迎点赞关注收藏，下次见~