Delete the target key K in the given binary search tree if the binary search tree contains K. Return the root of the binary search tree.

Find your own way to delete the node from the binary search tree, after deletion the binary search tree's property should be maintained.

Assumptions

• There are no duplicate keys in the binary search tree

Solution: recursion. 分3种情况：a. node没有child, 直接删掉；b. node有一child，把child连给parent；node有两child，先找大于该node的最小node，替换，并把右子树中这个node删掉

  public TreeNode delete(TreeNode root, int key) {
    if (root == null) {
      return root;
    }
    if (root.key < key) {
    //注意要赋值给root.right或者left
      root.right = delete(root.right, key);
    } else if (root.key > key) {
      root.left = delete(root.left, key);
    } else {
    //0或1 child情况
      if (root.left == null) {
        return root.right;
      }
      if (root.right == null) {
        return root.left;
      }
      //2 child情况
      TreeNode temp = root;
      //先找successor，并赋给root
      root = find_min_larger(temp.right);
      //如果successor与原root.right不同，要把右子树中该Node删掉
      if (root != temp.right) {
        root.right = delete_min(temp.right);
      }
      root.left = temp.left;
    }
    return root;
  }
  private TreeNode find_min_larger(TreeNode root) {
    if (root == null) {
      return root;
    }
    while (root.left != null) {
      root = root.left;
    }
    return root;
  }
  private TreeNode delete_min(TreeNode root) {
    if (root == null || root.left == null) {
      return root;
    }
    TreeNode cur = root.left, prev = root;
    while (cur.left != null) {
      prev = cur;
      cur = cur.left;
    }
    prev.left = cur.right;
    return root;
  }