java - 递归调用构建二叉搜索树的方法

Question

我正在尝试构建一个给定排序值的 ArrayList 的二叉搜索树。在尝试创建尽可能最有效的树时，我采用中间值，并将其添加到树中。然后递归地获取最左边的值并找到将其输入到树中的这些值的中间。

完成后，右侧也完成相同的操作。

我使用以下行调用balanceBST()方法:

balanceBST(iterator.list, 0, iterator.list.size() - 1);

假设 iterator.list 是一个包含值的整数 ArrayList:
{5、17、24、31、44、55、71、81、82、83、84、85、97}

public void balanceBST(ArrayList<E> values, int start, int end){
  int mid = (start + end) / 2;
  while(mid >= 0 && end > mid){ 
      insert(values.get(mid));
      balanceBST(values, start, mid - 1);
      balanceBST(values, mid + 1, end);
    }
}

insert(element) 方法完成将内容输入二叉树的相关工作。

这会产生各种错误，我认为当 mid 接近 0 或当 end 接近 mid 时它会发生困惑，但我自己遵循逻辑，但我不明白为什么会崩溃。

编辑:

对于那些将来阅读本文的人，非常感谢@David。以下解决了该问题:

  public void balanceBST(ArrayList<E> values, int start, int end){
  int mid = (start + end) / 2;
  if(end < 0 || start > end) return;
      insert(values.get(mid));
      balanceBST(values, start, mid - 1);
      balanceBST(values, mid + 1, end);
  }

Answer 1

当您对 BalanceBST 进行递归调用时，您不希望使用 while 循环，这会导致条目被重复插入。将 while 更改为终止测试并返回。注意仅插入 >= 0 和 < end，并在两者均为 false 时退出。