字节面试，HR给了道我做过的题，心中窃喜，但我假装不会，思考了两分钟，先给了非最优解，等面试官提示，再给了最优解，尺度把控可行？

// 登录 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
            if (root.right == null) return root.left;

            // 情况 3：被删除节点既有左子树，又有右子树
            // 比如 key 为 2
            //          5
            //       /     \
            //      2       6
            //    /   \       \
            //   1     4       7
            //        /
            //       3
            // 需要找到右子树最小的值，或者左子树中最大的值
            // 这里我们去找右子树最小的值，为 3
            TreeNode minNodeOfRight = findMinNode(root.right);

            // 找到右子树最小的值之后，修改当前节点 root 的值为右子树最小的值
            root.val = minNodeOfRight.val;
            
            // 同时，记得删除掉 root 的右子树最小的值之
            // 删除操作就是以 root 作为根节点，key 为右子树最小的值进行删除
            root.right = deleteNode(root.right, minNodeOfRight.val);
          
          // 3、如果 root 的节点值小于需要删除的值，那么就在 root 的右子树中去查找
        } else if (root.val < key) {
            // 在 root 的右子树中去查找并删除 key 
            root.right = deleteNode(root.right, key);

          // 4、如果 root 的节点值大于需要删除的值，那么就在 root 的左子树中去查找
        } else if (root.val > key) {
            // 在 root 的左子树中去查找并删除 key 
            root.left = deleteNode(root.left, key);
        }

        // 最后返回需要已经删除了 key 的二叉树的根节点
        return root;
    }

    // 通过 findMinNode ，可以找到二叉搜索树中最小的元素
    private TreeNode findMinNode(TreeNode node) {

        // 由于二叉搜索树，左子树所有元素的值都小于根节点的值
        // 所以可以不断的查找，直到为叶子节点，那么就找到了
        while (node.left != null) {
            // 不断的去查找当前节点的左子树
            node = node.left;
        }

        // 返回当前二叉搜索树中最小的元素
        return node;
    }
}