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.

Given binary search tree:

    5
   / \
  3   6
 / \
2   4

Remove 3, you can either return:

5
   / \
  2   6
   \
    4

or

5 
   / \
  4   6
 /
2

这题的思路应该分成两部分：

1. 找到那个Node和它的parent
2. 删除它

然后删除它又分成三种情况

1. 如果这个node 是个leave node (那么直接改掉它的子树reference 到null)
2. 如果这个node 有一个child (那么改掉它parents的reference 去它的child)
3. 如果这个node 有两个child

第三种情况是比较复杂的。这里我从这个reference搜到了一个思路就是说，找到这个node 右子树中最小的值，把这个node的value换成那个最小的值（注意不是换reference, 是换value), 然后删掉那个最小值的node(因为BST的特性，那个Node的左子树一定是空，这就转换成了第二种，或第一种情况）， 这貌似是个投机取巧的方法， 但是可以过OA， 不知道面试官是否会同意

具体的链接是这里，有详细的图示http://www.algolist.net/Data_structures/Binary_search_tree/Removal

有一个corner case因为要找的target node 有可能是root, 所以我们会new 一个dummy parent让它连到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 null;
        }
        TreeNode dummy = new TreeNode(0);
        dummy.left = root;
        TreeNode parent = findParent(dummy, root, value);
        TreeNode node;
        boolean isLeft = true;

        if (parent.left != null && parent.left.val == value) {
            node = parent.left;
        } else if (parent.right != null && parent.right.val == value) {
            node = parent.right;
            isLeft = false;
        } else {
            return dummy.left;
        }

        if (node.left == null && node.right == null) {
            parent.left = null;
            return dummy.left;
        } else if (node.right == null) {
            if (isLeft) {
                parent.left = node.left;
            } else {
                parent.right = node.left;
            }
            return dummy.left;
        } else if (node.left == null) {
            if (isLeft) {
                parent.left = node.right;
            } else {
                parent.right = node.right;
            }
            return dummy.left;
        }


        int smallestRight = findRightSmallest(node.right);


        TreeNode smallFather = findParent(parent, node, smallestRight);
        node.val = smallestRight;

        smallFather.left = null;


        return dummy.left;




    }

    public TreeNode findParent(TreeNode parent, TreeNode root, int value) {
        if (root == null) {
            return parent;
        }

        if (root.val == value) {
            return parent;
        }

        if (root.val > value) {
            return findParent(root, root.left, value);
        } else {
            return findParent(root, root.right, value);
        }
    }

    public int findRightSmallest(TreeNode node) {
        if (node.left == null) {
            return node.val;
        }

        return findRightSmallest(node.left);
    }
}

第二种是不太投机取巧的做法，但是思路是一样的，参考九章算法解答

就是还是去找右子树中最小值得node, 然后一路reference换下去。最后替换掉parent 的子树，然后替换上来的node的左右子树是找到的target node的左右子树。

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 null;
        }

        TreeNode dummy = new TreeNode(0);
        dummy.left = root;
        TreeNode parent = findParent(dummy, root, value);
        TreeNode node;
        if (parent.left != null && parent.left.val == value) {
            node = parent.left;
        } else if (parent.right != null && parent.right.val == value) {
            node = parent.right;
        } else {
            return dummy.left;
        }

        deleteNode(parent, node);

        return dummy.left;



    }

    public TreeNode findParent(TreeNode parent, TreeNode root, int value) {
        if (root == null) {
            return parent;
        }

        if (root.val == value) {
            return parent;
        }

        if (root.val > value) {
            return findParent(root, root.left, value);
        } else {
            return findParent(root, root.right, value);
        }
    }

    public void deleteNode(TreeNode parent, TreeNode node) {
        if (node.right == null) {
            if (parent.left == null) {
                parent.right = node.left;
            } else {
                parent.left = node.left;
            }
        } else {
            TreeNode temp = node.right;
            TreeNode father = node;
            while (temp.left != null) {
                father = temp;
                temp = temp.left;
            }
            if (father.left == temp) {
                father.left = temp.right;
            } else {
                father.right = temp.right;
            }
            if (parent.left == node) {
                parent.left = temp;
            } else {
                parent.right = temp;
            }
            temp.right = node.right;
            temp.left = node.left;
        }
    }
}