有序数组转 BST：中点做根，挡住偏斜
升序数组就是 BST 的中序。每次取区间中点当根，左右两侧人数至多差 1，高度被压在对数级。总拿端点当根会退化成链表。
区间 [lo, hi]：mid = lo+(hi−lo)/2 做根，左子树建 [lo, mid−1]，右子树建 [mid+1, hi]，lo>hi 返回空。中点保证左右元素数至多差 1，从而高度平衡。偶数长度偏左或偏右都合法。时间 O(n)，空间 O(log n)。
给你一个升序整数数组，把它转成一棵高度平衡的二叉搜索树。高度平衡：每个节点左右子树的高度差不超过 1。
主例 nums = [-10, -3, 0, 5, 9]。五个数已经有序。取中间的 0 做根，左边留给 [-10, -3]，右边留给 [5, 9]，两边再各自取中点。无论中点偏左还是偏右，根都是 0，整棵高度是 3，平衡。
按顺序一个个插入会得到一条右链，高度 5，不是本题要的树。本文要回答：为什么中点能挡住偏斜，以及偶数长度两种中点为什么都收。
中序已经有了，缺的是每次把区间劈成两半
BST 的中序遍历就是升序。输入已经是中序，节点值的左右关系不用再猜：区间里左边的数只能进左子树，右边的数只能进右子树。缺的是根选谁。根选得太偏，一侧元素远多于另一侧，高度就会被长的那侧拖高。
第一直觉是拿最小的当根、其余往右挂。主例会得到 -10 为根的一条右链，每个节点左空右一，高度差是 1 但整体高度是 5，叶子和根的高度差远超平衡。题目要的是每个节点都平衡，链状 BST 过不了。缺的不是「是不是 BST」，而是「左右人数尽量一样」。
人数尽量一样的切法就是取中点。mid = lo + (hi−lo)/2，nums[mid] 做根，左区间 [lo, mid−1]，右区间 [mid+1, hi]。左右长度至多差 1，再递归下去每层都减半，高度 O(log n)。空区间 lo > hi 返回空，这是叶子外侧的边界。
用手走主例。全区间 [0,4]，mid=2，值 0 做根。演示第一帧 mid 下标是 2，注释里的 0 是根的值。左区间 [0,1] 是 -10 和 -3，偏左中点下标 0，-10 做左子树根，-3 只能挂在它右边。右区间 [3,4] 是 5 和 9，偏左中点下标 3，5 做右子树根，9 挂右边。按这套中点，层序是 [0, -10, 5, null, -3, null, 9]。
偶数长度把中点改成偏右，左区间根会变成 -3（-10 挂左边），右区间根会变成 9（5 挂左边），层序是 [0, -3, 9, -10, null, 5]。演示最后一帧画的就是这种同样合法的平衡树。题目不要求唯一形态，两种都满足「每个节点左右高度差 ≤ 1」。不要把某一种中点当成唯一答案。
中点挡的是链总拿端点当根，有序插入会退化成链表。中点让两侧人数至多差 1，平衡是人数差逼出来的，不是事后旋转。
Go：区间递归
func sortedArrayToBST(nums []int) *TreeNode {var build func(int, int) *TreeNodebuild = func(lo, hi int) *TreeNode {if lo > hi { return nil }mid := lo + (hi-lo)/2return &TreeNode{Val: nums[mid],Left: build(lo, mid-1),Right: build(mid+1, hi),}}return build(0, len(nums)-1)}
1空区间返回空，必须写在取 mid 之前。
2偏左中点。主例全区间取到 0；左半取到 -10，右半取到 5。
3左右闭区间递归。每个数恰好当一次根，时间线性。
总结
有序数组当中序，中点当根，左右再切。主例根是 0，链状插法高度 5，中点法高度 3。
- 端点当根会退化成链表。中点让左右人数至多差 1。
- 偶数长度偏左、偏右都平衡。主例两种层序都合法。
- 空区间 lo>hi 返回空。空间是递归深度 O(log n)。