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.

分析：

这道题目其实是一个知识点，关于BST删除一个结点，有三种情况：

case (1) 这个结点没有child，那么直接删掉它就可以，让parent指向它的指针为NULL即可。

case (2) 这个结点只有1个child，那么让parent只想它的指针，指向他的child即可，这样做并不破坏BST性质。

case (3) 如果这个结点有2个children，那么问题就比较复杂

(a) 首先，要选右子树中最小的值的结点
(b) 然后，用这个最小值替换那个即将删掉的结点的值
(c) 最后，去右子树中删掉这个有最小值的结点

这样的做法是为了保证BST的性质，而且因为是右子树最小的点，这个点一定没有左孩子，所以case 3被化简为case 1或者case 2。同样的，你可以去左子树找最大值的结点，方法类似。

程序的逻辑：

1 找到这个要删掉的node，同时要记录他的parent。如果这个node不在root这棵树里，则直接返回。
2 如果是case 1或者case 2，判断parent是不是NULL。如果parent不是NULL，就可以直接进行删除了
如果parent是NULL说明这个要删除的点是root，所以要做特殊处理。
3 如果是case 3，则继续去右子树找min，同时继续移动parent。找到min后，先给之前要删除的点赋值，
然后删除那个min的结点。

reference:

http://www.algolist.net/Data_structures/Binary_search_tree/Removal
https://www.youtube.com/watch?v=gcULXE7ViZw

解法：

class Solution {
public:
    /**
     * @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.
     */
    void removeNodeHelper(TreeNode* parent, TreeNode* temp) {
        // case1, no child
        if (temp->left == NULL && temp->right == NULL) {
            if (parent->left == temp) {
                parent->left = NULL;
            } else {
                parent->right = NULL;
            }
        }
        // case 2, one child
        if (temp->left == NULL) {
            if (parent->left == temp) {
                parent->left = temp->right;
            } else {
                parent->right = temp->right;
            }
        }
        if (temp->right == NULL) {
            if (parent->left == temp) {
                parent->left = temp->left;
            } else {
                parent->right = temp->left;
            }
        }
    } 

    TreeNode* removeNode(TreeNode* root, int value) {
        // write your code here
        if (root == NULL) {
            return root;
        }
        TreeNode* parent = NULL;
        TreeNode* temp = root;
        // find the node to delete
        while (temp->val != value) {
            parent = temp;
            if (temp->val > value) {
                temp = temp->left;
            } else {
                temp = temp->right;
            }
            // if not in the BST
            if (temp == NULL) {
                return root;
            }
        }
        //case 3, two children
        if (temp->left != NULL && temp->right != NULL) {
            //find min in right sub-tree
            parent = temp;
            TreeNode* minRightSubTree = temp->right;
            while (minRightSubTree->left != NULL) {
                parent = minRightSubTree;
                minRightSubTree = minRightSubTree->left;
            }
            //replace temp value with that min
            temp->val = minRightSubTree->val;
            //remove that min node
            removeNodeHelper(parent, minRightSubTree);
        } else { 
            // special cases for deleting root node
            if (parent == NULL) {
                // case 1, no child
                if (temp->left == NULL && temp->right == NULL) {
                    return NULL;
                }
                // case 2, one child
                if (temp->left == NULL) {
                    return temp->right;
                }
                if (temp->right == NULL) {
                    return temp->left;
                }
            } else { // for deleting other nodes
                removeNodeHelper(parent, temp);
            }
        }
        return root;
    }
};