有序数组转高度平衡 BST 为什么用分治选中点？

简化版

有序数组转高度平衡 BST，可以每次选中间元素作为根。

中点左侧构造左子树，中点右侧构造右子树，这两个子问题结构完全相同。

因为每次左右规模接近一半，最终树高度是 O(log n)。

详细版

BST 的中序遍历是有序序列。给定升序数组，要构造平衡 BST，就应该让中间元素做根。

如果选最左或最右元素当根，树会退化成链表。选中点能让左右子树节点数量尽量接近，从而满足高度平衡。

递归函数 build(l, r) 表示用数组区间 [l, r] 构造一棵平衡 BST。

如果 l > r，返回 null；否则取 mid，创建根节点，再递归构造左右子树。

完整版教学

一、为什么 BST 和有序数组有关系

二叉搜索树满足左子树小于根、右子树大于根。对 BST 做中序遍历时，访问顺序正好是左、根、右，因此结果是升序。现在题目反过来给你升序数组，要求构造 BST，本质上是把有序序列还原成一种可能的树形结构。

记忆钩子：BST 的中序是升序；升序数组造 BST，就从中序还原一棵平衡形态。

二、为什么选中点作为根

高度平衡要求每个节点左右子树高度差不超过 1。数组中点左边和右边元素数量最接近，所以选中点做根能让左右子树规模平衡。如果选边界元素作为根，一边为空，一边有所有剩余元素，树会变成链。

根选择	左右规模	树形风险
最左元素	左 0，右 n-1	退化
最右元素	左 n-1，右 0	退化
中间元素	接近一半	高度平衡

中点选择正是分治均衡的体现。

三、递归定义怎么写

定义 build(l, r)：用 nums[l..r] 构造平衡 BST。

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

左右区间仍然是有序数组，所以子问题和原问题完全相同。

四、代码模板

实现如下：

function sortedArrayToBST(nums) {
  function build(l, r) {
    if (l > r) return null
    const mid = l + Math.floor((r - l) / 2)
    const root = new TreeNode(nums[mid])
    root.left = build(l, mid - 1)
    root.right = build(mid + 1, r)
    return root
  }
  return build(0, nums.length - 1)
}

如果数组长度为偶数，选左中点或右中点都可以，只要保持左右规模接近即可。

五、带数字例子

数组 [-10,-3,0,5,9]，中点是 0。

这只是其中一种合法结果。不同中点策略可能得到不同形状，但都可以是高度平衡 BST。

六、常见误区与追问

误区：按数组顺序逐个插入 BST。 升序插入会退化成链表，不平衡。
误区：认为结果唯一。 偶数长度时选左中点或右中点都可能合法。
误区：只保证 BST，不保证平衡。 题目要求高度平衡，根节点选择必须考虑规模。
追问：时间复杂度是多少？ 每个元素创建一次节点，时间 O(n)。
追问：空间复杂度是多少？ 递归栈高度是 O(log n)，不算输出树节点。

这些点都来自“有序性”和“平衡性”两个约束。

七、加强记忆

有序数组转 BST 记成“中点当根，左右递归”。中点保证左右规模接近，数组左侧天然属于左子树，右侧天然属于右子树。每个区间都用同样逻辑处理，因此是非常标准的分治题。不要按顺序插入，否则会把平衡树造成链表。

简化版

详细版