//    3種情況，
//            1.如果待刪除節(jié)點(diǎn)沒有子節(jié)點(diǎn)， 則直接刪除此節(jié)點(diǎn)；
//            2.如果有一個(gè)子節(jié)點(diǎn)，則這個(gè)子節(jié)點(diǎn)頂替當(dāng)前節(jié)點(diǎn)；
//            3.如果有兩個(gè)子節(jié)點(diǎn)，則取右子樹的最小節(jié)點(diǎn)（或左子樹最大節(jié)點(diǎn)）移到代替此節(jié)點(diǎn)
    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;
    }