将有序数组转换为二叉搜索树
Convert Sorted Array to Binary Search Tree
把升序数组转换成一棵高度平衡的二叉搜索树。
在力扣中练习题目描述
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
示例 1：
输入：nums = [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5] 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
示例 2：
输入：nums = [1,3] 输出：[3,1] 解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
提示：
1 <= nums.length <= 104-104 <= nums[i] <= 104nums按 严格递增 顺序排列
解题思路
主解法
中点分治 · 递归建树
取中点当根，左右两半各建一棵平衡 BST
BST 的中序遍历是升序，所以升序数组本身就是某棵 BST 的中序序列。要让树尽量平衡，根应当取当前区间的中点。
取 mid = (l + r) / 2 创建根，递归用 [l, mid-1] 建左子树、[mid+1, r] 建右子树。左右区间长度最多差 1，因此树高是 O(log n)。
分步图解
有序数组的中点是根，左边全部更小、右边全部更大；先建根，再递归两侧。
构造中的 BST · 浅色节点尚未创建
自拟数组有 7 个元素，根取下标 3 的 4；左区间 [−8,−3,0] 取 −3，右区间 [7,11,15] 取 11。这样每个节点的左右子树高度差不超过 1。
分步图解
区间 [4,6] 的中点 5，取 11 作为当前子树的根。
- mid
- 5
构造中的 BST · 浅色节点尚未创建
答案不唯一：偶数长度时取左中点或右中点都能得到合法平衡树，LeetCode 会校验任意合法答案。关键是每个节点都满足左小右大，并且高度平衡。
时间 O(n)空间 O(log n) 递归栈
易错点
- mid 写成 (l+r)/2 后忘记用局部变量：递归会覆盖上一层的中点。
- 区间写成左闭右闭却用 l < r：漏掉单元素区间。
- 取端点当根：树退化成链，不满足平衡要求。
代码与演示
演示输入
nums = [-8,-3,0,4,7,11,15]有序数组的中点是根，左边全部更小、右边全部更大；先建根，再递归两侧。
构造中的 BST · 浅色节点尚未创建
查看 C++ 代码
延伸阅读
- “有序数组 ↔ 平衡 BST”是同一份信息的两种表示，中点分治保证平衡。
- 如果数组含重复值，需要先明确重复元素放在左侧还是右侧，再决定边界。