## 题目

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1. Search for a node to remove.
2. If the node is found, delete the node.

Follow up: Can you solve it with time complexity O(height of tree)?

Example 1:

Example 2:

Example 3:

Constraints:

• The number of nodes in the tree is in the range [0, 10^4].
• -10^5 <= Node.val <= 10^5
• Each node has a unique value.
• root is a valid binary search tree.
• -10^5 <= key <= 10^5

## 思路

1. 被删除节点没有左子树：返回其右子树
2. 被删除节点节点没有右子树：返回其左子树
3. 被删除节点既有左子树，又有右子树：
1）查找到其右子树的最小值的节点，替换掉被删除的节点，并删除找到的最小节点
2）查找到其左子树的最大值的节点，替换掉被删除的节点，并删除找到的最大节点