本次刷题日记的第 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. 删除二叉搜索树中的节点
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
