利用二叉树的前序和中序重建二叉树

/**
 * BST树的节点类型
 * @param <T>
 */
class BSTNode <T extends Comparable<T>>{
    private T data; // 数据域
    private BSTNode<T> left; // 左孩子域
    private BSTNode<T> right; // 右孩子域

    public BSTNode(T data, BSTNode<T> left, BSTNode<T> right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public BSTNode<T> getLeft() {
        return left;
    }

    public void setLeft(BSTNode<T> left) {
        this.left = left;
    }

    public BSTNode<T> getRight() {
        return right;
    }

    public void setRight(BSTNode<T> right) {
        this.right = right;
    }
}

/**
 * BST树的实现
 * @param <T>
 */
class BST<T extends Comparable<T>>{
    private BSTNode<T> root; // 指向根节点

    /**
     * BST树的初始化
     */
    public BST() {
        this.root = null;
    }
    public void rebuild(T[] pre, T[] in) {
        this.root = rebuild(pre,0,pre.length-1,
                in,0,in.length-1);
    }

    private BSTNode<T> rebuild(T[] pre, int i, int j, T[] in, int m, int n) {
        if (i>j||m>n){
            return null;
        }
        BSTNode<T> node = new BSTNode<>(pre[i], null, null);

        for(int k=m; k<=n; ++k){
            // 在中序数组种找到根节点pre[i]         m, k-1   k+1,n
            if(pre[i].compareTo(in[k]) == 0){
                node.setLeft(rebuild(pre,i+1,i+(k-m),in,m,k-1));
                node.setRight(rebuild(pre,i+(k-m)+1,j,in,k+1,n));
                break;
            }
        }
        return node;
    }
}