Remove Node in Binary Search Tree

题目：

Given 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.

分析：

首先，逻辑要清晰

leaf怎么办
single child怎么办
double child怎么办

然后，注意special case

树里面就没有value怎么办
remove root怎么办

全都注意到了，题目就做出来了

解法：

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) {
        // write your code here
        if (root == null) {
            return root;
        }
        TreeNode prev = null;
        TreeNode curr = root;
        while (curr.val != value) {
            prev = curr;
            if (curr.val > value) {
                curr = curr.left;
            } else {
                curr = curr.right;
            }

            if (curr == null) { // not in the tree
                return root;
            }
        }

        if (prev == null) { // deal with removing root
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }
        }


        if (curr.left == null && curr.right == null) { // leaf node
            if (prev.left == curr) {
                prev.left = null;
            } else {
                prev.right = null;
            }
        } else if (curr.left == null) { // single child node
            if (prev.left == curr) {
                prev.left = curr.right;
            } else {
                prev.right = curr.right;
            }
        } else if (curr.right == null) {
            if (prev.left == curr) {
                prev.left = curr.left;
            } else {
                prev.right = curr.left;
            }
        } else { // double child node
            TreeNode next = curr.right;
            prev = curr;

            while (next.left != null) {
                prev = next;
                next = next.left;
            }

            curr.val = next.val;

            if (next.left == null && next.right == null) {
                if (prev.left == next) {
                    prev.left = null;
                } else {
                    prev.right = null;
                }
            } else if (next.left == null) {
                if (prev.left == next) {
                    prev.left = next.right;
                } else {
                    prev.right = next.right;
                }
            } else {
                if (prev.left == next) {
                    prev.left = next.left;
                } else {
                    prev.right = next.left;
                }
            }

        }
        return root;
    }
}