如何将一个有序数组转换成一棵平衡的二叉搜索树？

简化版

每次取数组中点作为根，中点左边的子数组递归建左子树、右边递归建右子树。因为数组有序，中点当根能保证左右两半节点数尽量相等，长出来的树自然高度平衡。这是分治思想，时间 O(n)。

详细版

有序数组本身就是一棵 BST 的中序遍历。要让树平衡，关键是让每棵子树的根都取子数组的中间元素，这样左右子树节点数差不超过 1，树高最小。

TreeNode sortedArrayToBST(int[] nums) {
    return build(nums, 0, nums.length - 1);
}
TreeNode build(int[] nums, int lo, int hi) {
    if (lo > hi) return null;
    int mid = lo + (hi - lo) / 2;          // 取中点作为根（防溢出写法）
    TreeNode root = new TreeNode(nums[mid]);
    root.left  = build(nums, lo, mid - 1); // 左半段建左子树
    root.right = build(nums, mid + 1, hi); // 右半段建右子树
    return root;
}

因为数组有序，左半段 < nums[mid] < 右半段，满足 BST 性质。
中点当根保证左右均衡，树高 O(log n)，是平衡 BST。

完整版教学

一、为什么中点当根就能平衡

树的高度由「最深的那条路径」决定。如果每次都用子数组的中间元素当根，那么左子树和右子树分到的元素个数几乎相等（差最多 1）。这样每往下一层，规模减半，树高就是 O(log n)——正是平衡的定义。反过来，如果不取中点（比如总取第一个元素当根），就会像「按序插入」一样退化成链。取中点 = 每次二分 = 平衡。

二、为什么天然满足 BST 性质

数组是升序的，对任意中点 mid：

它左边的子数组 [lo, mid-1] 里的值全都 < nums[mid]；
它右边的子数组 [mid+1, hi] 里的值全都 > nums[mid]。

这正好是 BST「左小右大」的要求。所以只要「左半段建左子树、右半段建右子树」，有序性自动成立，不需要额外比较。本质上是在复原一棵以该数组为中序遍历的 BST。

三、分治三步

这是标准的分治（Divide and Conquer）：

分：取中点，把数组分成左右两半。
治：递归地把左半、右半各自建成 BST。
合：中点是根，左右子树接上去。

递归出口是 lo > hi（空区间返回 null）。

四、中点的选择与树形

当子数组长度为偶数时，中点有两个候选（左中位、右中位）。选哪个都能得到合法的平衡 BST，只是树的形状略有不同：

mid = lo + (hi - lo) / 2 取偏左的中点。
mid = lo + (hi - lo + 1) / 2 取偏右的中点。

题目通常接受任意一棵合法答案。注意用 lo + (hi - lo) / 2 而不是 (lo + hi) / 2，避免大数组下标相加溢出。

五、复杂度与延伸

时间 O(n)：每个元素恰好被用来建一个节点一次。
空间 O(log n)：递归栈深度等于树高。
延伸：如果输入是有序链表而不是数组，不能 O(1) 取中点，可用快慢指针找中点（O(n log n)），或更巧地用中序模拟——按链表顺序「自底向上」构建，O(n)。

六、常见误区与追问

考点	正确口径
根的选择	取有序数组中点
左子树	递归处理中点左侧区间
右子树	递归处理中点右侧区间

build(l, r):
  mid = (l + r) / 2
  root = nums[mid]
  root.left = build(l, mid-1)
  root.right = build(mid+1, r)

有序数组转平衡 BST 的本质是“中点做根，左右区间天然保持有序”。

误区：直接按数组顺序插入 BST 就能平衡。 升序插入普通 BST 会退化成链表，必须用中点分治建树。
误区：只能选唯一一个中点。 偶数长度时选左中点或右中点都能得到合法平衡 BST，只是树形略不同。
误区：平衡 BST 要求左右节点数完全相等。 高度平衡只要求左右高度差不超过 1，中点分治能满足这一点。
追问：为什么天然满足 BST 性质？ 左区间所有值都小于中点，右区间所有值都大于中点，递归后每棵子树也满足。
追问：时间复杂度是多少？ 每个数组元素创建一个节点，时间 O(n)，递归栈 O(log n) 左右。
追问：如果输入是有序链表怎么办？ 可以快慢指针找中点递归，或先转数组；更优做法是模拟中序构建。

七、加强记忆

有序数组转平衡 BST：每次取中点当根，左半段递归建左子树、右半段建右子树。取中点保证左右均衡（每次二分 → 树高 O(log n) → 平衡）；数组有序保证「左 < 中 < 右」天然满足 BST。这是分治，O(n) 时间、O(log n) 空间。用 lo+(hi-lo)/2 防下标溢出。有序链表版可用快慢指针或中序自底向上构建。

简化版

详细版