class TreeNode {
    int val; //關(guān)鍵字
    TreeNode left; //左子節(jié)點(diǎn)
    TreeNode right; //右子節(jié)點(diǎn)
    
    public TreeNode(int val) {
        this.val = val;
    }
}

public class BST {
    private TreeNode root; //根結(jié)點(diǎn)
    
    public void insert(int val) { //插入新的節(jié)點(diǎn)
        
    }
    
    public void remove(int val) { //刪除對應(yīng)的節(jié)點(diǎn)
        
    }
    
    public boolean contains(int val) { //查詢是否有該值
        
    }
}

//遞歸解法
public void insert(int val) {
    root = process(val, root);
}

private TreeNode process(int val, TreeNode node) {
    if (node == null) { //如果當(dāng)前節(jié)點(diǎn)為null，說明已經(jīng)走到頭了，此時(shí)創(chuàng)建節(jié)點(diǎn)，返回即可
        return new TreeNode(val);
    } 
    if (val < node.val) { //小于當(dāng)前節(jié)點(diǎn)
        node.left = process(val, node.left);
    } else {
        node.right = process(val, node.right); //大于等于當(dāng)前節(jié)點(diǎn)
    }
    return node;
}

//非遞歸解法
public void insert(int val) {
    TreeNode node = new TreeNode(val); //先創(chuàng)建好節(jié)點(diǎn)
    TreeNode parent = null; //父節(jié)點(diǎn)，用于連接新的節(jié)點(diǎn)
    TreeNode cur = root; //當(dāng)前移動的節(jié)點(diǎn)
    
    if (root == null) {
        root = node; //還沒有根結(jié)點(diǎn)的情況
    } else {
        while (true) {
            parent = cur;
            if (val < cur.val) { //小于當(dāng)前節(jié)點(diǎn)的情況
                cur = cur.left;
                if (cur == null) { //如果為null了，說明走到了最后的節(jié)點(diǎn)
                    parent.left = node;
                    return;
                }
            } else { //大于當(dāng)前節(jié)點(diǎn)的情況
                cur = cur.right;
                if (cur == null) {
                    parent.right = node; //如果為null，就走到最后節(jié)點(diǎn)了
                    return;
                }
            }
        }
    }
}

//非遞歸版本
public boolean remove(int val) { //刪除對應(yīng)的節(jié)點(diǎn)
    if (root == null) {
        throw new RuntimeException("root is null.");
    }

    TreeNode parent = root;
    TreeNode cur = root;
    boolean isLeftChild = true;

    while (cur != null && cur.val != val) { //循環(huán)查找需要被刪除的節(jié)點(diǎn)
        parent = cur;
        if (val < cur.val) {
            cur = cur.left;
            isLeftChild = true;
        } else {
            cur = cur.right;
            isLeftChild = false;
        }
    }

    if (cur == null) { //沒找到需要刪除的節(jié)點(diǎn)
        return false;
    }

    //找到了需要被刪除的節(jié)點(diǎn)
    if ( cur.left== null && cur.right == null) { //葉節(jié)點(diǎn)的情況
        if (cur == root) {
            root = null;
        } else if (isLeftChild) {
            parent.left = null;
        } else {
            parent.right = null;
        }
    } else if (cur.right == null) {
        if (cur == root) {
            root = root.left;
        } else if (isLeftChild) {
            parent.left = cur.left;
        } else {
            parent.right = cur.left;
        }
    } else if (cur.left == null) { //只有一個(gè)孩子節(jié)點(diǎn)的情況
        if (cur == root) {
            root = root.right;
        } else if (isLeftChild) {
            parent.left = cur.right;
        } else {
            parent.right = cur.right;
        }
    } else { //有兩個(gè)孩子節(jié)點(diǎn)的情況
        TreeNode minNode = findMinNode(cur.right);
        if (cur == root) {
            root = minNode;
        } else if (isLeftChild) {
            parent.left = minNode;
        } else {
            parent.right = minNode;
        }
        minNode.left = cur.left; //新節(jié)點(diǎn)minNode的左孩子指向被刪除節(jié)點(diǎn)cur的左孩子
        // C/C++語言，需要回收cur內(nèi)存空間
    }
    return true;
}

private TreeNode findMinNode(TreeNode head)  {
    TreeNode pre = null;
    TreeNode cur = head;
    TreeNode next = head.left;
    while (next != null) {
        pre = cur;
        cur = next;
        next = next.left; //一直尋找該樹的最左的節(jié)點(diǎn)
    }
    if (pre != null) {
        pre.left = cur.right; //cur就是最左邊的節(jié)點(diǎn)，pre的cur的父節(jié)點(diǎn)。父節(jié)點(diǎn)的left指向cur的right
        cur.right = head; //cur的right指向head這個(gè)根結(jié)點(diǎn)
    }
    return cur; //返回最左邊的節(jié)點(diǎn)
}

//遞歸版本
public void remove2(int val) {
    if (root == null) {
        throw new RuntimeException("root is null.");
    }

    process2(val, root);
}

private TreeNode process2(int val, TreeNode node) {
    if (node == null) {
        return null;
    }
    if (val < node.val) { //小于
        node.left = process2(val, node.left);
    } else if (val > node.val){ //大于
        node.right = process2(val, node.right);
    } else if (node.left != null && node.right != null) { //上面的if沒成立，說明val相等。這里是兩個(gè)孩子節(jié)點(diǎn)的情況
        
        node.val = getMinNodeVal(node.right); //覆蓋右子樹中最小的節(jié)點(diǎn)值
        
        node.right = process2(node.val, node.right); // 重新對已經(jīng)覆蓋的數(shù)值進(jìn)行刪除
        
    } else { //只有一個(gè)孩子節(jié)點(diǎn)或者沒有節(jié)點(diǎn)的情況
        node = node.left != null? node.left : node.right;
    }
    return node;
}

private int getMinNodeVal(TreeNode node) {
    TreeNode pre = null;
    TreeNode cur = node;
    while (cur != null) {
        pre = cur;
        cur = cur.left;
    }
    return pre.val;
}

public boolean contains(int val) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val == val) {
            return true;
        } else if (val < cur.val) {
            cur = cur.left;
        } else {
            cur = cur.right;
        }
    }
    return false;
}