题目要求
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:Search for a node to remove.If the node is found, delete the node.Note: Time complexity should be O(height of tree).Example:root = [5,3,6,2,4,null,7]key = 3 5 / \ 3 6 / \ \2 4 7Given key to delete is 3. So we find the node with value 3 and delete it.One valid answer is [5,4,6,2,null,null,7], shown in the following BST. 5 / \ 4 6 / \2 7Another valid answer is [5,2,6,null,4,null,7]. 5 / \ 2 6 \ \ 4 7假设有一棵二叉搜索树，现在要求从二叉搜索树中删除指定值，使得删除后的结果依然是一棵二叉搜索树。
思路和代码
二叉搜索树的特点是，对于树中的任何一个节点，一定满足大于其所有左子节点值，小于所有其右子节点值。当删除二叉搜索树中的一个节点时，一共有三种场景：
- 该该节点为叶节点，此时无需进行任何操作，直接删除该节点即可
- 该节点只有一个子树，则将唯一的直接子节点替换掉当前的节点即可
- 该节点既有做左子节点又有右子节点。这时候有两种选择，要么选择左子树的最大值，要么选择右子树的最小值填充至当前的节点，再递归的在子树中删除对应的最大值或是最小值。
对每种情况的图例如下：
1. 叶节点 5 / \ 2 6 \ \ 4 7 （删除4）结果为： 5 / \ 2 6 \ 7 2. 只有左子树或是只有右子树 5 / \ 3 6 / \ \2 4 7（删除6）结果为 5 / \ 3 6 / \ 2 4 3. 既有左子树又有右子树 6 / \ 3 7 / \ \2 5 8 （删除6） / 4首先找到6的左子树中的最大值为5，将5填充到6的位置 5 / \ 3 7 / \ \2 5 8 （删除5） / 4接着递归的在左子树中删除5，此时5满足只有一个子树的场景，因此直接用子树替换即可 5 / \ 3 7 / \ \2 4 8 （删除5）代码如下：
public TreeNode deleteNode(TreeNode cur, int key) { if(cur == null) return null; else if(cur.val == key) { if(cur.left != null && cur.right != null) { TreeNode left = cur.left; while(left.right != null) { left = left.right; } cur.val = left.val; cur.left = deleteNode(cur.left, left.val); }else if(cur.left != null) { return cur.left; }else if(cur.right != null){ return cur.right; }else { return null; } }else if(cur.val > key) { cur.left = deleteNode(cur.left, key); }else { cur.right = deleteNode(cur.right, key); } return cur; }