450. 删除二叉搜索树中的节点

//    3种情况，
//            1.如果待删除节点没有子节点， 则直接删除此节点；
//            2.如果有一个子节点，则这个子节点顶替当前节点；
//            3.如果有两个子节点，则取右子树的最小节点（或左子树最大节点）移到代替此节点
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (key > root.val) {
            root.right = deleteNode(root.right, key);
            return root;
        } else if (key < root.val) {
            root.left = deleteNode(root.left, key);
            return root;
        } else {
            if (root.left == null) {
                TreeNode rightNode = root.right;
                root.right = null;
                return rightNode;
            }
            if (root.right == null) {
                TreeNode leftNode = root.left;
                root.left = null;
                return leftNode;
            }
            TreeNode rMin = minNode(root.right);
            rMin.right = removeMin(root.right);
            rMin.left = root.left;
            root.left = null;
            root.right = null;
            return rMin;
        }
    }

    public TreeNode minNode(TreeNode root) {
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }

    public TreeNode removeMin(TreeNode root) {
        if (root.left == null) {
            TreeNode rightNode = root.right;
            root.right = null;
            return rightNode;
        }
        root.left = removeMin(root.left);
        return root;
    }