题目描述
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点； 如果找到了，删除它。 说明： 要求算法时间复杂度为 $O(h)$，h 为树的高度。
示例
学习的东西
1 目标节点左右为空，直接删除
2 左右节点有一个为空一个不为空，就让不为空的做目标节点父节点的子树
3 左右节点都不为空(*)我自己的代码就是在这个地方变得又臭又长的，学习了大佬的方法，真没想到啊。。。
3.1 将目标节点的左子树移到目标节点中序遍历后继节点的左子树上
3.2 将目标节点的右子树移到目标节点中序遍历前驱节点的右子树上
我这里用的是3.1的方法。代码如下：
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root==null){
//代表当前树没有搜索到目标值，直接返回根节点即可
return root;
}
if(key==root.val){
if(root.left==null&&root.right==null){
return null;
}else if(root.left!=null&&root.right==null){
return root.left;
}else if(root.left==null&&root.right!=null){
return root.right;
}else{
TreeNode next= root.right;
while(next.left!=null){
next=next.left;
}
next.left=root.left;
root=root.right;
return root;
}
}
if(root.val>key){
root.left=deleteNode(root.left,key);
}else{
root.right=deleteNode(root.right,key);
}
return root;
}
}