[LintCode]Remove Node in Binary Search Tree

删除的时候三种情况：

• 没有子节点
• 有一个子节点
• 有两个子节点

三种情况和相应的删除方法如下图所示：

代码如下：

	/**
	* Definition of TreeNode:
	* public class TreeNode {
	* public int val;
	* public TreeNode left, right;
	* public TreeNode(int val) {
	* this.val = val;
	* this.left = this.right = null;
	* }
	* }
	*/
	public class Solution {
	/**
	* @param root: The root of the binary search tree.
	* @param value: Remove the node with given value.
	* @return: The root of the binary search tree after removal.
	*/
	public TreeNode removeNode(TreeNode root, int value) {
	if (root == null)
	return null;
	if (value < root.val)
	root.left = removeNode(root.left, value);
	else if (value > root.val)
	root.right = removeNode(root.right, value);
	else {
	if (root.left == null)
	return root.right;
	if (root.right == null)
	return root.left;
	TreeNode x = root;
	root = findMin(root.right);
	root.right = deleteMin(x.right);
	root.left = x.left;
	}
	return root;
	}
	}

view raw BST delete.java hosted with ❤ by GitHub

注意第26 - 29行非常简洁地处理了case 0 和 case 1，是值得背下来经常使用的。