大家好，我是吴师兄。
众所周知，人生如戏全靠演技，出门在外，咱们靠的都是一个“人设”，面试就是展示自己人设的一个场景，从面试进门的那个时刻起，我们就开始了职场“表演”，有的人想把自己塑造成技术高手，有的人想打造工作干练的形象。
而有的人却选择了反向操作
。
一位参加字节面试的同学面对熟悉的问题时，不直接给出答案，而是展现出层层思考、逐步优化的过程，这个操作确实容易让面试官参与进来进而加深其印象。
演技很好，可惜却被面试官识破
。
所以如果字节面试过程中如果遇到下方这种简单且熟悉的题目，
最好秒解
。
题目描述是这样的，给定一个二叉搜索树的根节点
root
和一个值
key
，删除二叉搜索树中的
key
对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
1、首先找到需要删除的节点；
2、如果找到了，删除它。
二叉搜索树（BST）是一种特殊的二叉树，对于任意节点，其左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值。
这个性质使得二叉搜索树在查找、插入和删除操作上有很好的性能
。
当需要在二叉搜索树中删除一个节点时，我们需要考虑以下几种情况：
-
节点不存在
：如果树为空，或者没有找到要删除的节点，什么也不做，直接返回
null
或原节点。
-
节点为叶子节点或只有一个子节点
：这种情况比较简单。
-
如果要删除的节点没有左子树，我们可以直接用其右子树替代该节点。
-
-
这实质上是将要删除节点的父节点直接连接到要删除节点的子节点上。
节点既有左子树又有右子树
：这种情况稍微复杂一点。
-
首先，找到要删除节点右子树中的最小节点（或左子树中的最大节点），这个节点将替代要删除的节点。
-
然后，将要删除节点的值替换为找到的最小（或最大）节点的值。
-
最后，删除原右子树中的最小节点（或左子树中的最大节点），因为它已经被移动到了要删除的节点的位置。
deleteNode(TreeNode root, int key)
方法是主要的逻辑实现，它递归地在二叉树中查找并删除指定值的节点。
如果找到了需要删除的节点
root.val == key
，根据上面的情况进行处理：
-
如果节点的左子树或右子树为空，直接用存在的子树替换当前节点。
-
如果节点既有左子树又有右子树，则需要找到右子树的最小节点（通过
findMinNode(TreeNode node)
方法），用这个最小节点的值替换当前节点的值，然后删除右子树中的这个最小节点。
-
如果当前节点的值小于需要删除的值，则在右子树中继续查找；如果大于，则在左子树中查找。
-
findMinNode(TreeNode node)
方法用于找到以
node
为根的子树中的最小值节点。由于二叉搜索树的性质，这个最小值节点肯定在最左边，因此通过不断访问左子节点直到
null
即可找到最小值节点。
通过这种方式，可以有效地在二叉搜索树中删除任意一个节点，同时保持二叉搜索树的性质不变。
代码如下：
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 删除二叉搜索树中的节点（ LeetCode 450 ）:https://leetcode-cn.com/problems/delete-node-in-a-bst/
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
// 1、如果 root 为空，那么直接返回空
if (root == null) return null;
// 2、如果 root 的节点值等于需要删除的值，那么需要根据以下几种情况进行处理
if (root.val == key) {
// 情况 1：当前节点的左子树为空，那么当前节点 root 由 root 的右子树占位就行
// 比如 key 为 7
// 6
// / \
// 2 7
// \
// 8
// 直接将以 8 作为根节点的二叉树挪到 7 的位置
// 6
// / \
// 2 8
if (root.left == null) return root.right;
// 情况 2：当前节点的右子树为空，那么当前节点 root 由 root 的左子树占位就行
// 比如 key 为 2
// 6
// / \
// 2 7
// /
// 1
// 直接将以 1 作为根节点的二叉树挪到 2 的位置
// 6
// / \
// 1 7
