public class BST<Key extends Comparable<Key>,Value> {		//E 要满足Comparable接口，要有可比较性
    private class Node {	//声明对应的节点类型
        private Key key;
        private Value value;
        private Node left, right;

        public Node(Key key,Value value) {
            this.key = key;	    //e为用户传来的e
            this.value = value;	//左孩子初始化
            left = right = null;	//右孩子初始化
        }
    }

    private Node root;	//根节点root
    private int count;	//count 记录当前二叉树存储元素的数量

    public BST(){	//二分搜索树的构造函数
        root = null;
        count = 0;
    }
    //返回二分搜索树的节点个数
    public int size(){
        return count;
    }
    //返回二分搜索树是否为空
    public boolean isEmpty(){	//二分搜索树为空
        return count == 0;
    }
}

// 向二分搜索树中添加新的元素e
    public void insert(Key key,Value value){

        if(root == null){
            root = new Node(e);		//根节点直接指向新建的元素即可
            count ++;
        }
        else
            insert(root, key ,value);	//从根节点添加新元素e
    }

    // 向以node为根的二分搜索树中插入元素e，递归算法
    private void insert(Node node, Key key ,Value value){	//传入参数 Node 与 e
        if(key.compareTo(node.key)==0)	//【递归的终止条件1】传入的key已经存在于树中
            node.value = value;
            return;
        else if(key.compareTo(node.key) < 0 && node.left == null){	
            //【递归的终止条件2】插入的key比node节点中的key小，且左子树为空
            node.left = new Node(key,value);	//插入左子树中，直接让node的左孩子为新插入的e
            count ++;
            return;
        }
        else if(key.compareTo(node.key) > 0 && node.right == null){
            //【递归的终止条件3】插入的key比Node节点中的key大且右子树为空
            node.right = new Node(key,value);//插入右子树中，直接让node的右孩子为新插入的e
            count ++;
            return;
        }

        if(key.compareTo(node.key) < 0)	//递归调用，插入的e比Node节点中的e小，e插入左子树
            insert(node.left, key,value);
        else //e.compareTo(node.e) > 0
            insert(node.right, key,value);	//node 的右孩子成为元素e
    }

// 向以node为根的二分搜索树中插入元素e，递归算法
// 返回插入新节点后二分搜索树的根 
private Node insert(Node node,Key key,Value value){
    if(node == null){	//只要node 为null,则必须新插入节点
        count ++;
        return new Node(key,value); //将节点与二叉树挂接起来
    }
    if(key.compareTo(node.key)==0)
        node.value = value;
    else if(e.compareTo(node.e) < 0)
        node.left = insert(node.left, e);	//传入的key小于当前节点，则用递归函数将其插入到node的左子树中
    else // key.compareTo(node.key) > 0
        node.right = insert(node.right, e);
    return node;   //最后把以node为根的树返回回去
    }
}

// 看二分搜索树中是否包含元素e（新增代码）
public boolean contain(Key key){
    return contain(root,key); //从根节点开始查看
}

// 查看以node为根的二分搜索树中是否包含键值为key的节点, 使用递归算法
private boolean contain(Node node,Key key){
    
    if(node == null) //[递归出口1]如果传入的node为空直接返回false
        return false;
    if(key.compareTo(node.key) == 0) //[递归出口2]如果传入的key与node的key相等则找到，返回true
        return ture;
    else if(key.compareTo(node.key) < key) //如果传入的key小于node的key，则向递归函数中传入node的左子节点，进行递归调用
        return contain(node.left,key);
    else //key.compareTo(node.key)>0
        return contain(node.right,key);
}

public Value search(key key){
    return search(root,key);//从根节点开始搜索
}
// 在以node为根的二分搜索树中查找key所对应的value, 递归算法
// 若value不存在, 则返回NULL
private Value search(Node node,Key key){
    
    if(node == null)  //[递归出口1]如果传入的node为空直接返回false
        return null;
    if(key.compareTo(node.key)==0) //[递归出口2]如果传入的key与node的key相等则找到，返回node.value
        return node.value;
    else if(key.compareTo(node.key)<0) //如果传入的key小于node的key，则向递归函数中传入node的左子节点，进行递归调用
        return search(node.left,key);
    else //key.compareTo(node.key)>0
        return search(node.right,key);
}

public void preOrder(){
    preorder(root); //从根节点开始
}
// 对以node为根的二叉搜索树进行前序遍历, 递归算法
private void preOrder(Node node){
    if(node !=null){ //在node不为空的情况下，则进行遍历
        System.out.println(node.key);
        preOrder(node.left);
        preOrder(node.right);
    }
}

public void inOrder(){
    inOrder(root);
}
private void inOrder(Node node){
    if(node != null){
        inOrder(node.left);
        System.out.println(node.key);
        inOrder(node.right);
    }
}

public void postOrder(){
    postOrder();
}
private void postOrder(Node node){
    postOrder(node.left);
    postOrder(node.right);
    System.out.println(node.key);
}

public void levelOrder(){
    //我们使用LinkedList来作为我们的队列
    ListedList<Node> q = new LinkedList<Node>();
    q.add(root);
    while(! q.isEmpty()){
        
        Node node = q.remove();//当前节点出队
        System.out.println(node.key); //打印当前节点的key
        
        if(node.left != null)
            q.add(node.left);
        if(node.right != null)
            q.add(node.right);            
    }
}

// 寻找二分搜索树的最小的键值
public Key minimum(){
    assert count != 0;  //只要二分搜索树不为空
    Node minNode = minimum( root );
    return minNode.key;
        
}
// 返回以node为根的二分搜索树的最小键值所在的节点
private Node minimum(Node node){
    if( node.left == null )  //递归出口
        return node;         //若该节点左子节点为空，则直接返回其自身

    return minimum(node.left); //其左子节点不为空，则递归调用其左子节点
}


// 寻找二分搜索树的最大的键值
public Key maximum(){
    assert count != 0;
    Node maxNode = maximum(root);
    return maxNode.key;
}

// 返回以node为根的二分搜索树的最大键值所在的节点
private Node maximum(Node node){
     if( node.right == null )
        return node;

     return maximum(node.right);
    }

// 从二分搜索树中删除最小值所在节点
    public void removeMin(){
        if( root != null )
            root = removeMin( root );
    }

    // 从二分搜索树中删除最大值所在节点
    public void removeMax(){
        if( root != null )
            root = removeMax( root );
    }
  private Node removeMin(Node node){

        if( node.left == null ){  //递归出口。如果当前节点的左孩子为空则当前节点就是最小节点

            Node rightNode = node.right;  //把node节点的右孩子，作为原来node节点的父节点的左孩子
            node.right = null;     
            count --;                     
            return rightNode;    //用当前node的右孩子代替了node
        }

        node.left = removeMin(node.left); //当前节点左孩子不为空，则递归调用。
        return node;
    }

    // 删除掉以node为根的二分搜索树中的最大节点
    // 返回删除节点后新的二分搜索树的根
    private Node removeMax(Node node){

        if( node.right == null ){

            Node leftNode = node.left;
            node.left = null;
            count --;
            return leftNode;
        }

        node.right = removeMax(node.right);
        return node;
    }

// 从二分搜索树中删除键值为key的节点
    public void remove(Key key){
        root = remove(root, key);
    }
// 删除掉以node为根的二分搜索树中的最小节点
    // 返回删除节点后新的二分搜索树的根
    private Node remove(Node node, Key key){

        if( node == null )
            return null;

        if( key.compareTo(node.key) < 0 ){
            node.left = remove( node.left , key );
            return node;
        }
        else if( key.compareTo(node.key) > 0 ){
            node.right = remove( node.right, key );
            return node;
        }
        else{   // key == node->key

            // 待删除节点左子树为空的情况
            if( node.left == null ){
                Node rightNode = node.right;
                node.right = null;
                count --;
                return rightNode;
            }

            // 待删除节点右子树为空的情况
            if( node.right == null ){
                Node leftNode = node.left;
                node.left = null;
                count--;
                return leftNode;
            }

            // 待删除节点左右子树均不为空的情况

            // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            // 用这个节点顶替待删除节点的位置
            Node successor = new Node(minimum(node.right));
            count ++;

            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;
            count --;

            return successor;
        }
    }

// 测试二分搜索树
    public static void main(String[] args) {

        int N = 1000000;

        // 创建一个数组，包含[0...N)的所有元素
        Integer[] arr = new Integer[N];
        for(int i = 0 ; i < N ; i ++)
            arr[i] = new Integer(i);

        // 打乱数组顺序
        for(int i = 0 ; i < N ; i ++){
            int pos = (int) (Math.random() * (i+1));
            Integer t = arr[pos];
            arr[pos] = arr[i];
            arr[i] = t;
        }
        
        // 我们测试用的的二分搜索树的键类型为Integer，值类型为String
        // 键值的对应关系为每个整型对应代表这个整型的字符串
        BST<Integer,String> bst = new BST<Integer,String>();
        for(int i = 0 ; i < N ; i ++)
            bst.insert(new Integer(arr[i]), Integer.toString(arr[i]));

        // 对[0...2*N)的所有整型测试在二分搜索树中查找
        // 若i在[0...N)之间，则能查找到整型所对应的字符串
        // 若i在[N...2*N)之间，则结果为null
        for(int i = 0 ; i < 2*N ; i ++){
            String res = bst.search(new Integer(i));
            if( i < N )
                assert res.equals(Integer.toString(i));
            else
                assert res == null;
        }
    }

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {//传入头结点和要删除元素所包含的节点。 
        while(head != null && head.val == val){
            ListNode delNode = head;  //定义待删除的节点
            head = head.next;         //绕过我们要删除的节点
            delNode.next = null;      
        }
        if(head == null)
            return null;              //也许该链表中所有节点都是要被删除的节点
        
        ListNode prev = head;         //找到待删除元素前一个节点
        while(prev.next ！= null){    
            if(prev.next.val == val){ //删除prev.next但是prev不用向后挪。
                ListNode delNode = prev.next;
                prev.next = delNode.next;
                delNode = null;
            }
            else
                prev = prev.next;    //prev向后挪一位
        }
        
        return head;
    }
}

private class Node{         //用户不需要知道底层是如何实现的，因此设置为私有类。
    public E e;             //data
    public Node next;       //指向下一个Node的引用。自引用。
    
    public Node(E e,Node next){ //声明构造函数，用户也同时传来 e 和 next
        this.e = e;             //声明构造函数，用户也同时传来 e 和 next
        this.next = next;       //将当前节点的next赋值成用户传来的next
    }
    public Node(E e){           //用户只传来e
        this(e,null);           //将当前节点的e赋值成用户传来的e，next设为null
    }
    public Node(){              //用户什么都不传
        this(null,null);        //将e和next都设为null
    }
    @Override
    public String toString(){ //重写toString方法
        e.toString();
    }
}

public class LinkedList<E> {
 
    private class Node{
        public E e;
        public Node next;
 
        public Node(E e, Node next){
            this.e = e;
            this.next = next;
        }
 
        public Node(E e){
            this(e, null);
        }
 
        public Node(){
            this(null, null);
        }
 
        @Override
        public String toString(){
            return e.toString();
        }
    }
	//（新增代码）
    private Node head;	//声明Node型变量head
    private int size;	//size记录链表中有多少个元素
 
    public LinkedList(){	//构造函数，链表初始化时的head与size
        head = null;
        size = 0;
    }
 
    // 获取链表中的元素个数（新增代码）
    public int getSize(){
        return size;
    }
 
    // 返回链表是否为空（新增代码）
    public boolean isEmpty(){
        return size == 0;
    }
 
    // 在链表头添加新的元素e（新增代码） 
    public void addFirst(E e){
//        Node node = new Node(e); //创建新的节点 e
//        node.next = head;		//让 node 的 next 指向现在链表的头
//        head = node;			//让 head  指向新的节点
 
        head = new Node(e, head);	//上面三行代码的优雅写法
        size ++;
    }
 
    // 在链表的index(0-based)位置添加新的元素e（新增代码）
    // 在链表中不是一个常用的操作，练习用：）
    public void add(int index, E e){		
 
        if(index < 0 || index > size)	//判断 index 的合法性
            throw new IllegalArgumentException("Add failed. Illegal index.");
 
        if(index == 0)
            addFirst(e);
        else{
            Node prev = head;	
            for(int i = 0 ; i < index - 1 ; i ++)
                prev = prev.next;		
			//把当前 prev 存的下一个节点放到 prev 变量中，prev会在链表中一直移动，直到 index - 1 这个位置
 
//            Node node = new Node(e);		//创建node,元素为 e
//            node.next = prev.next;		//将 node 的 next 指向 prev 的下一个元素
//            prev.next = node;				//prev 的 next 指向 node
 
            prev.next = new Node(e, prev.next);		//上面三行的优雅写法
            size ++;
        }
    }
 
    // 在链表末尾添加新的元素e（新增代码）
    public void addLast(E e){
        add(size, e);
    }
}

public class LinkedList<E> {
 
    private class Node{
        public E e;
        public Node next;
 
        public Node(E e, Node next){
            this.e = e;
            this.next = next;
        }
 
        public Node(E e){
            this(e, null);
        }
 
        public Node(){
            this(null, null);
        }
 
        @Override
        public String toString(){
            return e.toString();
        }
    }
 
    private Node dummyHead;		//引入虚拟头结点（修改代码）
    private int size;
 
    public LinkedList(){
        dummyHead = new Node();//（修改代码）
        size = 0;
    }
 
    // 获取链表中的元素个数
    public int getSize(){
        return size;
    }
 
    // 返回链表是否为空
    public boolean isEmpty(){
        return size == 0;
    }
 
    // 在链表的index(0-based)位置添加新的元素e
    // 在链表中不是一个常用的操作，练习用：）
    public void add(int index, E e){
 
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Illegal index.");
 
        Node prev = dummyHead;	//
        for(int i = 0 ; i < index ; i ++)		//找到 index 位置的前一个节点
            prev = prev.next;	//prev 初始时是从 dummyHead 开始的（修改代码）
 
        prev.next = new Node(e, prev.next);
        size ++;
    }
 
    // 在链表头添加新的元素e
    public void addFirst(E e){
        add(0, e);		//（修改代码）直接复用 add 即可
    }
 
    // 在链表末尾添加新的元素e
    public void addLast(E e){
        add(size, e);
    }
}

 // 获得链表的第index(0-based)个位置的元素
    // 在链表中不是一个常用的操作，练习用：）
    public E get(int index){

        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed. Illegal index.");

        Node cur = dummyHead.next;
        for(int i = 0 ; i < index ; i ++)
            cur = cur.next;
        return cur.e;
    }

    // 获得链表的第一个元素
    public E getFirst(){
        return get(0);
    }

    // 获得链表的最后一个元素
    public E getLast(){
        return get(size - 1);
    }

    // 修改链表的第index(0-based)个位置的元素为e
    // 在链表中不是一个常用的操作，练习用：）
    public void set(int index, E e){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed. Illegal index.");

        Node cur = dummyHead.next;
        for(int i = 0 ; i < index ; i ++)
            cur = cur.next;
        cur.e = e;
    }

    // 查找链表中是否有元素e
    public boolean contains(E e){
        Node cur = dummyHead.next;
        while(cur != null){
            if(cur.e.equals(e))
                return true;
            cur = cur.next;
        }
        return false;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();

//        Node cur = dummyHead.next;
//        while(cur != null){
//            res.append(cur + "->");
//            cur = cur.next;
//        }
        for(Node cur = dummyHead.next ; cur != null ; cur = cur.next)
            res.append(cur + "->");
        res.append("NULL");

        return res.toString();
    }
}

public class Main {

    public static void main(String[] args) {

        LinkedList<Integer> linkedList = new LinkedList<>();
        for(int i = 0 ; i < 5 ; i ++){
            linkedList.addFirst(i);
            System.out.println(linkedList);
        }

        linkedList.add(2, 666);
        System.out.println(linkedList);
    }
}

public E remove(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        Node prev = dummyHead;
        for(int i = 0 ; i < index ; i ++)
            prev = prev.next;

        Node retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;
        size --;

        return retNode.e;
    }

    // 从链表中删除第一个元素, 返回删除的元素
    public E removeFirst(){
        return remove(0);
    }

    // 从链表中删除最后一个元素, 返回删除的元素
    public E removeLast(){
        return remove(size - 1);
    }

    // 从链表中删除元素e
    public void removeElement(E e){

        Node prev = dummyHead;
        while(prev.next != null){
            if(prev.next.e.equals(e))
                break;
            prev = prev.next;
        }

        if(prev.next != null){
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size --;
        }
    }

import java.util.Stack
public class Solution{
      public boolean isVaild(String s){
             Stack<Character> stack = new Stack<>(); //声明这个栈
             for(int i = 0;i<s.length();i++){ //遍历字符串
                 char c = s.charAt(i); //查看字符串中第i个字符是什么样子的，存成char c
                 if（c == '('|| c=='[' || c=='{'）
                      stack.push(c); //如果符合条件，则push压入栈中，以便后期pop出来匹配
                 else{
                     if(stack.isEmpty()) //如果没有要匹配的字符串
                         return false;
                     char topChar = stack.pop();//pop使元素出栈，将栈顶元素存入topChar中
                     //如果不能匹配成功
                     if(c == ')' && topChar != '(')
			   //如果检索到的符号和pop出的符号无法匹配则失败
			    	     return false;
			         if(c == ']' && topChar != '[')
			    	     return false;
			         if(c == '}' && topChar != '}')
			    	     return false;
                 }
             }
             //如果栈为空则匹配成功
             return stack.isEmpty();
      }
}

public void enqueue(E e){
    
    if((tail+1)%data.length == front) //如果队列已经满了(已经转了一圈了)
        resize(2*data.length);        //进行扩容
    
    data[tail] = e;                   //把元素加到队尾
    tail = (tail+1)%data.length;      //队尾下标加一，并对数组长度取余数，以便循环。
    size++;  
}

public E dequeue(){
    if(isEmpty())                      //如果队列为空，则抛出异常
        throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
    E ret = data[front];               //把要删除的元素存在ret中
    data[front] = null;
    front = (front+1) % data.length;   //front向后移动一位，为了实现循环，因此对长度取余数
    size--;
                                       //进行缩容，以免空间被浪费
    if(size == getCapacity()/4 && getCapacity()/2 != 0 )
        resize(getCapacity()/2);
    return ret;
}

public void resize(int newCapacity){
    E[] newData =(E[]) new Object[newCapacity+1];
    for(int i = 0;i < size;i++)
        newData[i] = data[(i+front)%data.length];
    data = newData;
    front = 0;
    tail = size;
}

public class LoopQuene<E>{            //支持泛型
    private E[] data;
    private int front,tail;           //队首和队尾的下标
    private int size;                 //元素的数量
    
    public LoopQuene(int capacity){   //有参的构造方法
        data = (E[]) new Object[capacity+1]; //新建一个泛型数组
        front = 0;                    //此时队列中没有元素
        tail = 0;                     
        size = 0;
    }
    public LoopQuene(){               //无参的构造方法
        this(10);
    }
    public int getCapacity(){         //队列的容量
        return data.length-1;
    }
    public boolean isEmpty(){         //是否为空
        return front == tail;
    }
    public int getSize(){             //队列中元素的个数
        return size;
    }
    public void enqueue(E e){         //入队
        if((front+1)%data.length == tail)
            resize(2*data.length);
        data[tail] = e;
        tail = (tail+1)%data.length;
        size++;
    }
    public E dequeue(){               //出队
        if(isEmpty())                 //若队列为空，则抛出异常
            throw new IllegalArgument("");
        E ret = data[front];
        front = (front+1)%data.length; //front向前移动
        data[front] = null;            //将front对应元素设置为null，真正删除
        size--;                        //元素数量减少
        
        if(getCapacity == size/4 && getCapacity) //缩容，但是缩容的这个值不应该为0
            resize(getCapacity/2);
        return ret;
    }
    public void resize(int newCapacity){
        E[] newData = (E[])new Object[newCapacity+1];
        for(int i =0;i<size;i++)      //解释同上
            newData[i] = data[(i+front)%data.length];  
        data = newData;
        front = 0 ;
        tail = size;
    }
    public E getFront(){              //得到队首元素
        if(isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return data[front];
    }
}

class HighArray{
    private long[] data;    //ref to array data
    private int size;  //number of data items
    
    public HighArray(int max){    //constructor
        data = new long[max];     //creat the array
        size = 0;                 //no items yet
    }
    public boolean find(long searchKey){ //find specified value
        int j;                    
        for(j=0;j<nElems;j++){        //for each elements     
            if(data[j] == searchKey)  //found items?
                break;                //exit loop before end gone to end?
        }
        if(j == size)           
            return false;          //can't found it
        else
            return true;           // found it
    }
     public void insert(long value){ //put elements into array 
         data[size] = value;         //insert it
         nElems ++;                  //increamnt size 
     }
    public boolean delete(long value){
        int j;
        for (j=0 ;j<size ;j++)     //look for it
            if(value == a[j])      
                break;
        if(j == size)
            return false;          //can't find it
        else
            for(int k=j;k< size;k++)
                a[k] = a[k+1];      //move higher ones down
            size--;                 //decrement size
            return true;
    }  
    public void display(){
        for(int j =0;j<nElems;j++)        //for each elements
            System.out.println(a[j]+" "); //display for it
    }
}

public void add(int index,int e){
    //先判断index是否越界
    if(index < 0|| index> size)
        throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
    //如果数组元素个数与长度相等，需要扩容
    if(size == data.length)
        resize(2*data.length);
    //把数组中从最后到index位置的元素都向后挪动一位，再把index位置中的元素赋值成e
    for(int i = size; i >= index ;i--)
        data[i+1] = data[i];
    data[index] = e;
    size++;
}

public void resize(int capacity){
    int[] newData = new int[capacity];
    for(int i = 0;i< size; i++)
        newData[i] = a[i];
    a = newData;
}

public int remove(int index){
    if(index <0 || index>size)
        throw new IllegalArgumentException("Remove failed. Index is illegal.");
    //保存要删除位置的元素，以便返回
    int ret = data[index];
    //从下标index+1开始到size-1，用后一个位置的元素去覆盖前一个位置的元素，就把index位置元素挤出去了。
    for(int i = index+1;i<size;i++)
        data[i-1] = data[i];
    size--;
    
    //为了避免数组空间有所浪费，因此进行缩容
    if(size == data.length/2)
        resize(data.length/2);
    return ret;
}

public void removeElement(int e){
    int index = find(e);
    if(index != -1)//如果没有找到
        remove(index);
}

@Override
public String toString(){
      StringBuilder res = new StringBuilder();
      res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
      res.append('[');
      for(int i = 0 ; i < size ; i ++){
          res.append(data[i]);
          if(i != size - 1)         //如果不是最后一个元素
              res.append(", ");
        }
      res.append(']');
      return res.toString();
}

public int find(long searchKey){
    int lowerBound = 0;
    int upperBound = nElems-1;
    int curIn;
    while(true){
        curIn = (lowerBound+upperBound)/2;
        if(a[curIn] == searchKey)
            return curIn;
        else if(lowerBound>upperBound)
            return nElems;
        else{
            if(a[curIn]<searchKey)
                lowerBound = curIn+1;  //it's in upper half
            else
                upperBound = curIn -1; //it's in lower half
        }
    }
}