如何通过数组中间值递归构建平衡二叉搜索树（BST）

看起来你正在用分治法从有序数组构建平衡二叉搜索树（BST），这种思路非常正确——通过每次取当前子数组的中间元素作为根，能保证左右子树的节点数量尽可能均衡，最终得到高度平衡的BST。

完整代码实现 #

结合你给出的代码框架，我补全了逻辑，并且调整了中间索引的计算方式来匹配你期望的插入序列：

public static BST fillBST(BST b, List<Integer> nums, int start, int end) {
    // 递归终止条件：当前子数组没有元素，直接返回
    if (start > end) {
        return b;
    }
    
    // 计算右中间索引（匹配你给出的7,3,1...的插入序列）
    // 如果想选左中间，改成 (start + end) / 2 即可
    int mid = (start + end + 1) / 2;
    
    // 将当前中间元素插入BST（假设BST类有insert方法）
    b.insert(nums.get(mid));
    
    // 递归处理左半部分子数组
    fillBST(b, nums, start, mid - 1);
    // 递归处理右半部分子数组
    fillBST(b, nums, mid + 1, end);
    
    return b;
}

关键细节说明 #

• 递归终止条件：当start > end时，说明当前子数组为空，不需要插入任何元素，直接返回即可。
• 中间索引的选择：
  • 你给出的例子中，第一个插入的是7（数组长度14，索引7是右中间元素），所以用(start + end + 1) / 2来计算右中间索引。
  • 如果选择左中间元素（比如第一个插入6），则用(start + end) / 2，两种方式都能构建平衡BST，只是节点插入顺序不同。
• 递归顺序：先插入中间元素，再递归处理左子数组，最后处理右子数组，完全匹配你期望的序列。

执行流程验证（对应你的示例数组） #

对于数组[0,1,2,3,4,5,6,7,8,9,10,11,12,13]，执行流程如下：

• 初始调用：start=0, end=13 → mid=(0+13+1)/2=7 → 插入7
• 左子数组start=0, end=6 → mid=(0+6+1)/2=3 → 插入3
• 左子数组start=0, end=2 → mid=(0+2+1)/2=1 → 插入1
• 左子数组start=0, end=0 → mid=0 → 插入0
• 右子数组start=2, end=2 → mid=2 → 插入2
• 回到左子数组的右半部分start=4, end=6 → mid=(4+6+1)/2=5 → 插入5
• 左子数组start=4, end=4 → 插入4
• 右子数组start=6, end=6 → 插入6
• 后续会继续处理初始右子数组start=8, end=13，依次插入11、9、8、10、13、12，完全符合你期望的序列。

调用示例 #

你可以这样调用这个方法来构建平衡BST：

import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> nums = Arrays.asList(0,1,2,3,4,5,6,7,8,9,10,11,12,13);
        BST balancedBST = fillBST(new BST(), nums, 0, nums.size() - 1);
        // 这里可以添加代码验证BST的结构是否平衡
    }
}

内容的提问来源于stack exchange，提问作者Marsilinou Zaky