京公网安备11010502063487号给定一个升序排列的整数数组，构造一棵高度平衡的二叉搜索树。正确做法是每次取当前区间的中点当根，递归处理左右两半，因为区间两侧元素数最多相差 1，构造出的树天然平衡。一个常见陷阱是：既然数组有序，就把它按顺序逐个插入一棵初始为空的 BST——这确实满足 BST 性质，但因为每个新值都比已有的都大，只会不断往右挂，退化成一条链，完全不平衡。本文用真实的规模对比验证这个规律，给出正确写法、5 种语言实现，以及取中点分治的分步演示。
本文只用自己的话概括题意，完整约束以官方页面为准。给定一个升序排列的整数数组，构造一棵高度平衡的二叉搜索树（本题允许多种正确答案，只要满足 BST 性质且高度平衡即可）。一共 5 组用例，覆盖：官方示例、空数组、单元素、两元素、七元素的完全填满情况：
[-10, -3, 0, 5, 9] → [0,-10,5,null,-3,null,9] [] → [] [1] → [1] [1, 2] → [1,null,2] [1, 2, 3, 4, 5, 6, 7] → [4,2,6,1,3,5,7]
一个真实会犯的错误：既然数组已经排好序了，有人会想"那就按顺序一个个插入一棵二叉搜索树"——这确实能得到一棵合法的 BST（中序遍历还原出来就是原数组），但完全不满足"高度平衡"的要求。因为数组本来就是升序的，按顺序插入时每个新值都比当前树里所有值大，只会不断往右边挂，结果是一条纯右链，退化成链表：
输入 1..15（15 个有序整数）\n正确写法（取中点分治） → 高度 4，平衡\n陷阱写法（顺序插入 BST） → 高度 15，不平衡
用一组不断增大的有序数组验证这个规律：
规模 n 与两种写法的树高：\nn= 1 正确写法高度=1(平衡=True) 陷阱写法高度= 1(平衡=True)\nn= 3 正确写法高度=2(平衡=True) 陷阱写法高度= 3(平衡=False)\nn= 7 正确写法高度=3(平衡=True) 陷阱写法高度= 7(平衡=False)\nn= 15 正确写法高度=4(平衡=True) 陷阱写法高度= 15(平衡=False)\nn= 31 正确写法高度=5(平衡=True) 陷阱写法高度= 31(平衡=False)\nn= 63 正确写法高度=6(平衡=True) 陷阱写法高度= 63(平衡=False)\nn=127 正确写法高度=7(平衡=True) 陷阱写法高度=127(平衡=False)
正确写法的高度始终是 ⌈log₂(n+1)⌉ 左右，陷阱写法的高度始终等于 n——因为数组有序，顺序插入这个操作对 BST 来说是最坏情况，每次都插在同一侧。只有当 n 很小（比如只有 1 个元素）时，两种写法碰巧看起来差不多，规模一大问题就暴露了。
分治：每次取当前区间 [l, r] 的中间元素 nums[(l+r)/2] 作为这一段的根，左半区间递归构造左子树，右半区间递归构造右子树。因为数组本身有序，中间元素两侧元素个数最多相差 1，这样递归下去每个结点的左右子树高度差也最多是 1，天然满足"高度平衡"。时间 O(n)，空间 O(log n)（递归栈）。Python、Java、Go、JavaScript、C++ 都是真实编译运行的，用同一组 5 个测试用例。
Python · 解法代码def sorted_array_to_bst(nums): def helper(l, r): if l > r: return None mid = (l + r) // 2 root = TreeNode(nums[mid]) root.left = helper(l, mid - 1) root.right = helper(mid + 1, r) return root return helper(0, len(nums) - 1)
$ python3 solution.py [-10, -3, 0, 5, 9] → [0,-10,5,null,-3,null,9] [] → [] [1] → [1] [1, 2] → [1,null,2] [1, 2, 3, 4, 5, 6, 7] → [4,2,6,1,3,5,7]
Java · 解法代码class Solution { public TreeNode sortedArrayToBST(int[] nums) { return helper(nums, 0, nums.length - 1); } private TreeNode helper(int[] nums, int l, int r) { if (l > r) return null; int mid = (l + r) / 2; TreeNode root = new TreeNode(nums[mid]); root.left = helper(nums, l, mid - 1); root.right = helper(nums, mid + 1, r); return root; } }
$ javac -d build Main.java && java -cp build Main [-10, -3, 0, 5, 9] → [0,-10,5,null,-3,null,9] [] → [] [1] → [1] [1, 2] → [1,null,2] [1, 2, 3, 4, 5, 6, 7] → [4,2,6,1,3,5,7]
Go · 解法代码func sortedArrayToBST(nums []int) *TreeNode { var helper func(l, r int) *TreeNode helper = func(l, r int) *TreeNode { if l > r { return nil } mid := (l + r) / 2 root := &TreeNode{Val: nums[mid]} root.Left = helper(l, mid-1) root.Right = helper(mid+1, r) return root } return helper(0, len(nums)-1) }
$ go run solution.go [-10, -3, 0, 5, 9] → [0,-10,5,null,-3,null,9] [] → [] [1] → [1] [1, 2] → [1,null,2] [1, 2, 3, 4, 5, 6, 7] → [4,2,6,1,3,5,7]
JavaScript · 解法代码function sortedArrayToBST(nums) { function helper(l, r) { if (l > r) return null; const mid = Math.floor((l + r) / 2); const root = new TreeNode(nums[mid]); root.left = helper(l, mid - 1); root.right = helper(mid + 1, r); return root; } return helper(0, nums.length - 1); }
$ node run.js [-10, -3, 0, 5, 9] → [0,-10,5,null,-3,null,9] [] → [] [1] → [1] [1, 2] → [1,null,2] [1, 2, 3, 4, 5, 6, 7] → [4,2,6,1,3,5,7]
C++ · 解法代码class Solution { public: TreeNode* sortedArrayToBST(vector<int>& nums) { return helper(nums, 0, (int)nums.size() - 1); } private: TreeNode* helper(vector<int>& nums, int l, int r) { if (l > r) return nullptr; int mid = (l + r) / 2; TreeNode* root = new TreeNode(nums[mid]); root->left = helper(nums, l, mid - 1); root->right = helper(nums, mid + 1, r); return root; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin [-10, -3, 0, 5, 9] → [0,-10,5,null,-3,null,9] [] → [] [1] → [1] [1, 2] → [1,null,2] [1, 2, 3, 4, 5, 6, 7] → [4,2,6,1,3,5,7]
共 5 组用例（含边界），以 Python 结果为基准逐组比对：\n Python 通过 5/5\n Java 通过 5/5\n Go 通过 5/5\n JavaScript 通过 5/5\n C++ 通过 5/5
Python 版本另外做了一次针对"取中点分治"写法本身的随机验证：对每一棵构造出来的树，检查两件事——是不是高度平衡，以及中序遍历回去是不是能精确还原原数组（BST 性质的直接体现）。
随机验证 30,000 组（数组长度 0 到 50 的随机升序数组），构造出的树全部满足「高度平衡」且「中序遍历还原原数组」，0 组不满足。
另外四种语言只在上面 5 组固定用例上验证过，没有做大规模随机验证。
下面的演示用官方示例 [-10,-3,0,5,9]：每一步取当前区间的中点作为根，左半区间递归构造左子树，右半区间递归构造右子树，因为两侧元素个数最多相差 1，构造出来的树天然是高度平衡的。蓝色是当前正在处理的区间，绿色是已经放进树里的结点。每一帧都是把上面的解法在这组输入上真实执行记录下来的。