LeetCode问题描述：
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 7 Given 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 7 Another valid answer is [5,2,6,null,4,null,7]. 5 / \ 2 6 \ \ 4 7题目大意是说给定某一个排序二叉树（BST）和一个Key值，要求删除此排序二叉树中与Key值相等的节点，之后返回此BST的根节点。 分析如下：
这一步是最基础的，一般大家会想到利用BST的性质直接进行查找，但是在这里可能会有点问题（后面会讲到）。
分三种情况——该节点无子节点、该节点有1个子节点、该节点有2个子节点。
①无子节点： 在这种情况下，我们这需做一个判断——如果该节点为根节点，则直接返回null； 否则，对其父节点中该节点赋值null，并返回root（根节点）。
②有1个子节点： 判断——如果该节点为root节点，直接返回其子节点；否则，对其父节点中该节点赋值为该节点的子节点，并返回root。
③有2个子节点： 这种情况最复杂，先找到该节点右子树的最小节点，并将此最小节点与该节点进行值交换，然后删除找到的这个最小节点。 注：这里递归删除时会有一些问题，因为虽然原二叉树是BST，但将节点的值进行交换后，顺序改变，就不再是BST了，所以一中不应该使用BST的查找算法，而应该采用遍历查找。
实现代码如下（Java）：
class TreeNode{ int val;//节点值 TreeNode left; TreeNode right; TreeNode(int x){ this.val = x; } } class Solution{ //输出第level层的节点的值 public int showTreeValueAtLevel(TreeNode node , int level){ if(level < 0) return 0;//如果node为空或者level<0，直接结束 else if(node == null){ System.out.print("null "); return 0; } else if(level == 0 && node != null){ System.out.print(node.val+" "); return 1;//level == 0时即为找到了此节点 } return showTreeValueAtLevel(node.left, level-1)+showTreeValueAtLevel(node.right, level-1); } public void levelTravelsal(TreeNode node){ int i;//遍历的层数 for(i = 0;;i++){ if(showTreeValueAtLevel(node, i)==0)//终止遍历条件 break; System.out.println(); } } public TreeNode deleteNode(TreeNode root, int key) { if(root == null) return null; TreeNode father = searchFatherNode(root, key); TreeNode desNode;//目标节点 desNode = getDesNode(root, father, key); System.out.println("father:"+father); if(desNode == null){ return root; }else{ if(desNode.left == null && desNode.right == null){ //目标节点存在且无子节点 if(desNode == root) return null; else if(father.left == desNode) father.left = null; else father.right = null; }else if(desNode.left != null && desNode.right == null ){ //目标节点存在且只有左节点 if(desNode == root)//如果是根结点,直接返回其子节点 return desNode.left; desNode.val = desNode.left.val; if(father.left == desNode) father.left = desNode.left; else father.right = desNode.left; }else if(desNode.right != null && desNode.left == null){ //目标节点存在且只有右节点 if(desNode == root)//如果是根结点,直接返回其子节点 return desNode.right; desNode.val = desNode.right.val; if(father.left == desNode) father.left = desNode.right; else father.right = desNode.right; }else{ //目标节点有左右子节点 // System.out.println("currDesNode:"+desNode.val); TreeNode minNode = getMinNode(desNode.right); // System.out.println("minNode:"+minNode.val); Swap(desNode, minNode); return deleteNode(root, key); } return root; } } //交换两节点的值 public void Swap(TreeNode node1, TreeNode node2){ int temp = node1.val; node1.val = node2.val; node2.val = temp; } //从根结点出发,返回最小的节点 public TreeNode getMinNode(TreeNode root){ if(root.left != null) return getMinNode(root.left); return root; } //找出符合条件的节点的父节点 public TreeNode searchFatherNode(TreeNode root, int key){ if(root == null) return null; if(root.left != null && root.left.val == key) return root; else if(root.right != null && root.right.val == key) return root; //继续找 TreeNode resNode; if(root.left != null){ resNode = searchFatherNode(root.left, key); if(resNode != null) return resNode; } if(root.right != null){ resNode = searchFatherNode(root.right, key); if(resNode != null) return resNode; } return null; } public TreeNode getDesNode(TreeNode root,TreeNode father, int key){ if(father == null){ if(root.val == key)//目标节点就是根结点 return root; else return null;//目标节点不存在 }else{ //如果father不为空,则目标节点一定存在; if(father.left != null && father.left.val == key) return father.left; else return father.right; } } }