java - 来自已排序数组的 BST 列表

Question

这是我实验室提出的问题，我被难住了。我们基本上得到一个已经排序的数组，我们必须使用这个数组来创建列表格式的 BST。 (这看起来怎么样)？这是我到目前为止的代码，但它根本不起作用，我不知道如何修复它:

    private static void buildBalancedRec(Integer [] tempArr, int start, int end,
        BinarySearchTreeList<Integer> bstList)
{       
    if (bstList.size()<tempArr.length){
        Integer middle  = tempArr[(start+end)/2];
        bstList.add(middle);
        buildBalancedRec(tempArr, start , middle-1 , bstList);
        buildBalancedRec(tempArr, middle+1, end, bstList);
}

假设我们得到的数组是{1,2,3,4,5,6,7}。开始为 1，结束为 7。我假设 BST 列表应该如下所示:{4, 2, 6, 1, 3, 5, 7}，这是正确的吗？ BST 看起来像:

        4
       / \
      2   6
     /\   /\
    1 3   5 7

所以我推测列表会是什么样子。

我怎样才能到达那里？我可以像当前代码中那样有两行背对背递归吗？

我尝试了很多方法，但我永远无法让它打印 {4, 2, 6, 1, 3, 5, 7}。

任何指导将不胜感激!

注意:该方法需要使用递归

Answer 1

尝试:

private static void buildBalancedRec(int[] tempArr, int start, int end, BinarySearchTreeList<Integer> list) {
    if (start < end) {
        int middle = (start + end) / 2;
        list.add(tempArr[middle]);
        buildBalancedRec(tempArr, start, middle, list);
        buildBalancedRec(tempArr, middle + 1, end, list);
    }
}

编辑:

完整示例:

private static void buildBalancedRec(int[] tempArr, int start, int end, List<Integer> list) {
    if (start < end) {
        int middle = (start + end) / 2;
        list.add(tempArr[middle]);
        buildBalancedRec(tempArr, start, middle, list);
        buildBalancedRec(tempArr, middle + 1, end, list);
    }
}

public static void main(String[] args) {
    int[] tempArr = {1, 2, 3, 4, 5, 6, 7};
    List<Integer> list =new ArrayList<>(tempArr.length);
    buildBalancedRec(tempArr, 0, tempArr.length, list);
    System.out.println(list);
}

它打印:

[4, 2, 1, 3, 6, 5, 7]