public class BinarySearchTree {
    private TreeNode root; //存放根節(jié)點(diǎn)
    private static class TreeNode {
        private int val;
        private TreeNode left;
        private TreeNode right;
        private TreeNode(int val) {
            this.val = val;
        }
    }
}

public boolean insert(int key) {
    // 二叉搜索樹沒有節(jié)點(diǎn)的情況
    if (root == null) {
        root = new TreeNode(key);
        return true;
    }
    // 二叉搜索樹不為空的情況 -> 找到該節(jié)點(diǎn)要插入的位置進(jìn)行插入
    // 如果已經(jīng)存在該節(jié)點(diǎn)了, 則不用插入 -> 二叉搜索樹中不能出現(xiàn)重復(fù)值
    TreeNode parent = null; // 記錄cur的父節(jié)點(diǎn)
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val < key) {
            parent = cur;
            cur = cur.right;
        } else if (cur.val > key) {
            parent = cur;
            cur = cur.left;
        } else {
            return false; // 插入重復(fù)的節(jié)點(diǎn)
        }
    }
    // 走到這, cur為空了, key 需要插入到 parent 的左節(jié)點(diǎn)或右節(jié)點(diǎn)中
    TreeNode newNode = new TreeNode(key);
    if (parent.val < key) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }
    return true;
}

public TreeNode search(int key) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val < key) {
            cur = cur.right;
        } else if (cur.val > key) {
            cur = cur.left;
        } else {
            return cur;
        }
    }
    return null;
}

public boolean remove(int key) {
    TreeNode parent = null;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val < key) {
            parent = cur;
            cur = cur.right;
        } else if (cur.val > key) {
            parent = cur;
            cur = cur.left;
        } else {
            removeNode(parent, cur);
            return true;
        }
    }
    return false;
}
private void removeNode(TreeNode parent, TreeNode cur) {
    if (cur.left == null) {
        if (cur == root) {
            root = cur.right;
        } else if (cur == parent.left) {
            parent.left = cur.right;
        } else {
            parent.right = cur.right;
        }
    } else if (cur.right == null) {
        if (cur == root) {
            root = cur.left;
        } else if (cur == parent.left) {
            parent.left = cur.left;
        } else {
            parent.right = cur.left;
        }
    } else {
        TreeNode target = cur.right;
        TreeNode targetParent = cur;
        while (target.left != null) {
            targetParent = target;
            target = target.left;
        }
        // 走到這, target就是要?jiǎng)h除節(jié)點(diǎn)的右子樹中最小的節(jié)點(diǎn), 接下來(lái)進(jìn)行覆蓋
        cur.val = target.val;
        // 覆蓋完成, 現(xiàn)在需要?jiǎng)h除 target 節(jié)點(diǎn)
        // 如果 cur.right 沒有左孩子的情況, 此時(shí)的target就是cur.right
        // 即直接將 cur.right 覆蓋到 cur 位置, 也就是滿足 target == targetParent.right 條件
        // 所以需要進(jìn)行特殊處理.
        if (target == targetParent.right) {
            targetParent.right = target.right;
        } else {
            targetParent.left = target.right;
        }
    }
}