给定一个二叉搜索树的根节点 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
    输出: []
    �
    二叉树特点：
    1）左子树所有的节点值都比根节点的值小
    2）右子树所有的节点值都比根节点的值大

    若要删除一个节点，则需要先找到这个节点，然后进行删除操作：
    1）如果值比当前节点值小，则继续往左子树找
    2）如果值比当前节点值大，则继续往右子树找
    3）如果值等于当前节点的值，则表示找到目标节点，进行节点删除操作
    �

    1. public TreeNode deleteNode(TreeNode root, int key) {
    2.     if (root.val == key) {
    3.        // 找到目标，进行节点删除操作
    4.     }
    5.     if (key < root.val) {
    6.         // 去左子树找
    7.         root.left = deleteNode(root.left, key);
    8.     }
    9.     if (key > root.val) {
    10.         // 去右子树找
    11.         root.right = deleteNode(root.right, key);
    12.     }
    13.     return root;
    14. }

    那删除一个二叉搜索树中的节点，该怎么删除呢？怎么找到代替被删除的节点呢？

    假设二叉搜索树如下：

    1.       4                     4                4               4                4
    2.     /   \                 /   \            /   \           /   \            /   \
    3.   2       6     ---->   2       6         2     6         2     6          2     6
    4.  / \     / \             \     / \       /     / \       / \     \        / \    /
    5. 1   3   5   7             3   5   7     1     5   7     1   3     7      1   3  5

    如果需要删除的节点没有子节点-节点 1 或者 3 或者 5 或者 7，那么直接删除即可

    1. if (root.left == null && root.right == null) {
    2.     root = null;
    3. }

    假设二叉搜索树如下：

    1.      4                      4
    2.    /   \                  /   \
    3.   2     6       ----->   3     6
    4.    \   / \                    / \
    5.     3 5   7                  5   7
    7.      4                      4
    8.    /   \                  /   \
    9.   2     6       ----->   1     6
    10.  /     / \                    / \  
    11. 1     5   7                  5   7

    如果需要删除的节点有一个子节点-节点 2 ，那么让子节点代替自己

    1. if (root.left == null || root.right == null) {
    2.     if (root.left == null) {
    3.         root = root.right;
    4.     }
    5.     if (root.right == null) {
    6.         root = root.left;
    7.     }
    8. }

    假设二叉搜索树如下：

    1.       4                    
    2.     /   \                
    3.   2       6    
    4.  / \     / \             
    5. 1   3   5   7

    如果需要删除的节点有两个子节点-节点 4 ，那么该怎么删除呢？
    如果从左子树中找，则需要找到左子树中节点值最大的节点，然后让其代替被删除的节点

    1.       4                      3
    2.     /   \                  /   \
    3.   2       6     ----->   2      6
    4.  / \     / \            /      /  \
    5. 1   3   5   7          1      5    7
    1. if (root.left != null && root.right != null) {
    2.     // 找到左子树最大的节点
    3.     TreeNode leftMaxNode = root.left;
    4.     while (leftMaxNode.right != null) {
    5.         leftMaxNode = leftMaxNode.right;
    6.     }
    7.     // 左子树删除左子树最大的节点
    8.     root.left = deleteNode(root.left, leftMaxNode.val);
    9.     // 用 leftMaxNode 代替 root
    10.     leftMaxNode.left = root.left;
    11.     leftMaxNode.right = root.right;
    12.     root = leftMaxNode;
    13. }

    如果从右子树中找，则需要找到右子树中节点值最小的节点，然后让其代替被删除的节点

    1.      4                     5
    2.    /   \                 /   \
    3.   2      6     ----->   2     6
    4.  / \    / \            / \     \
    5. 1   3  5   7          1   3     7
    1. if (root.left != null && root.right != null) {
    2.     // 找到右子树最小的节点
    3.     TreeNode rightMinNode = root.right;
    4.     while (rightMinNode.left != null) {
    5.         rightMinNode = rightMinNode.left;
    6.     }
    7.     // 右子树删除右子树最小的节点
    8.     root.right = deleteNode(root.right, rightMinNode.val);
    9.     // 用 leftMaxNode 代替 root
    10.     rightMinNode.left = root.left;
    11.     rightMinNode.right = root.right;
    12.     root = rightMinNode;
    13. }

    完整算法

    1. public TreeNode deleteNode(TreeNode root, int key) {
    2.     if (root == null) {
    3.         return null;
    4.     }
    5.     if (root.val == key) {
    6.         // 找到目标，进行节点删除
    7.         // 如果目标节点是末子节点，直接删除即可
    8.         if (root.left == null && root.right == null) {
    9.             // 结束查找
    10.             return null;
    11.         }
    12.         // 如果目标节点有一个子节点，让子节点代替自己
    13.         if (root.left == null || root.right == null) {
    14.             if (root.left == null) {
    15.                 root = root.right;
    16.             }
    17.             if (root.right == null) {
    18.                 root = root.left;
    19.             }
    20.             // 结束查找
    21.             return root;
    22.         }
    23.         // 如果目标节点有两个子节点，不能直接代替，需要从左子树和右子树中选择出新的根节点
    24.         // 假设从左子树找
    25.         if (root.left != null && root.right != null) {
    26.             // 找到左子树最大的节点
    27.             TreeNode leftMaxNode = root.left;
    28.             while (leftMaxNode.right != null) {
    29.                 leftMaxNode = leftMaxNode.right;
    30.             }
    31.             // 左子树删除左子树最大的节点
    32.             root.left = deleteNode(root.left, leftMaxNode.val);
    33.             // 用 leftMaxNode 代替 root
    34.             leftMaxNode.left = root.left;
    35.             leftMaxNode.right = root.right;
    36.             root = leftMaxNode;
    37.         }
    38.     }
    39.     if (key < root.val) {
    40.         // 去左子树
    41.         root.left = deleteNode(root.left, key);
    42.     }
    43.     if (key > root.val) {
    44.         // 去右子树
    45.         root.right = deleteNode(root.right, key);
    46.     }
    47.     return root;
    48. }
    1. public TreeNode deleteNode(TreeNode root, int key) {
    2.     if (root == null) {
    3.         return null;
    4.     }
    5.     if (root.val == key) {
    6.         // 找到目标，进行节点删除
    7.         // 如果目标节点是末子节点，直接删除即可
    8.         if (root.left == null && root.right == null) {
    9.             // 结束查找
    10.             return null;
    11.         }
    12.         // 如果目标节点有一个子节点，让子节点代替自己
    13.         if (root.left == null || root.right == null) {
    14.             if (root.left == null) {
    15.                 root = root.right;
    16.             }
    17.             if (root.right == null) {
    18.                 root = root.left;
    19.             }
    20.             // 结束查找
    21.             return root;
    22.         }
    23.         // 如果目标节点有两个子节点，不能直接代替，需要从左子树和右子树中选择出新的根节点
    24.         // 假设从右子树找
    25.         if (root.left != null && root.right != null) {
    26.             // 找到右子树最小的节点
    27.             TreeNode rightMinNode = root.right;
    28.             while (rightMinNode.left != null) {
    29.                 rightMinNode = rightMinNode.left;
    30.             }
    31.             // 右子树删除右子树最小的节点
    32.             root.right = deleteNode(root.right, rightMinNode.val);
    33.             // 用 leftMaxNode 代替 root
    34.             rightMinNode.left = root.left;
    35.             rightMinNode.right = root.right;
    36.             root = rightMinNode;
    37.         }
    38.     }
    39.     if (key < root.val) {
    40.         // 去左子树
    41.         root.left = deleteNode(root.left, key);
    42.     }
    43.     if (key > root.val) {
    44.         // 去右子树
    45.         root.right = deleteNode(root.right, key);
    46.     }
    47.     return root;
    48. }