Lintcode: Remove Node in Binary Search Tree

iven a root of Binary Search Tree with unique value for each node.  Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You should keep the tree still a binary search tree after removal.

Have you met this question in a real interview? Yes
Example
Given binary search tree:

          5

       /    

    3          6

 /    

2       4

Remove 3, you can either return:

          5

       /    

    2          6

      

         4

or :

          5

       /    

    4          6

 /   

2

分析：假设当前node 为root

1. if value < root.val, 要被删除的节点在左子树，往左子树递归，并把操作结束后的返回值作为新的root.left

2. if value > root.val, 要被删除的节点在右子树，往右子树递归, 并把操作结束后的返回值作为新的root.right

3. if root == null, 递归到了一个null点，说明要删的value不存在，return null，而这个null点的parent的相应子树本来也是null，对树的结构没有任何影响

4. if value == root.val，说明root是该被删除的了

　　A. if root.left == null, return root.right

　　B. if root.right == null, return root.left(这两个case其实包含了只有一个child和一个child都没有的三种情况)

　　C. 如果两个children都存在，从右子树中找最小的node，与root交换，再递归调用函数在右子树中删除root.val

 1 /**
 2  * Definition of TreeNode:
 3  * public class TreeNode {
 4  *     public int val;
 5  *     public TreeNode left, right;
 6  *     public TreeNode(int val) {
 7  *         this.val = val;
 8  *         this.left = this.right = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     /**
14      * @param root: The root of the binary search tree.
15      * @param value: Remove the node with given value.
16      * @return: The root of the binary search tree after removal.
17      */
18     public TreeNode removeNode(TreeNode root, int value) {
19         // write your code here
20         if (root == null) return null;
21         if (value < root.val)  
22             root.left = removeNode(root.left, value);
23         else if (value > root.val)
24             root.right = removeNode(root.right, value);
25         else {
26             if (root.left == null) return root.right;
27             if (root.right == null) return root.left;
28             TreeNode minOfRight = findMin(root.right);
29             //swap root and minOfRight
30             int temp = root.val;
31             root.val = minOfRight.val;
32             minOfRight.val = temp;
33             root.right = removeNode(root.right, minOfRight.val);
34         }
35         return root;
36     }
37     
38     public TreeNode findMin(TreeNode cur) {
39         while (cur.left != null) {
40             cur = cur.left;
41         }
42         return cur;
43     }
44 }