将有序数组转换为二叉搜索树
给你一个整数数组 nums，其中元素已经按 严格递增 顺序排列。请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡二叉树指一棵二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
示例
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案。
输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
提示
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums按 严格递增 顺序排列
解法一（递归取中点）：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right)
* : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return build(nums, 0, nums.size() - 1);
}
private:
TreeNode* build(vector<int>& nums, int left, int right) {
if (left > right) {
return nullptr;
}
int mid = left + (right - left) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = build(nums, left, mid - 1);
root->right = build(nums, mid + 1, right);
return root;
}
};
核心思想
有序数组天然对应二叉搜索树的中序遍历结果。
如果想让树尽量平衡，就不能总是选数组的一端作为根节点，而应该每次选择当前区间的中间元素作为根节点：
- 中点左侧的所有元素都小于根节点，递归构造左子树。
- 中点右侧的所有元素都大于根节点，递归构造右子树。
- 因为左右区间长度最多只相差
1，所以构造出的左右子树高度也会尽量接近。
为什么满足二叉搜索树
对于任意递归区间 [left, right]：
- 选择
mid位置的元素nums[mid]作为根节点。 - 区间
[left, mid - 1]中的元素都小于nums[mid]。 - 区间
[mid + 1, right]中的元素都大于nums[mid]。
因此，左子树所有节点值都小于根节点，右子树所有节点值都大于根节点，递归构造后整棵树就是二叉搜索树。
为什么高度平衡
每次递归都把当前区间从中间拆成左右两部分。
设当前区间长度为 len，那么左右子区间长度分别大约为：
len / 2len / 2
两边节点数量最多相差 1，递归下去后，任意节点的左右子树规模都尽量接近，因此整棵树高度平衡。
递归边界
当 left > right 时，说明当前区间为空，没有节点可以构造，返回 nullptr。
if (left > right) {
return nullptr;
}
执行过程
以 nums = [-10,-3,0,5,9] 为例：
区间 [0,4]，中点 2，根节点为 0
左区间 [0,1]，中点 0，左子树根节点为 -10
右区间 [3,4]，中点 3，右子树根节点为 5
继续递归：
- [-3] 成为 -10 的右子节点
- [9] 成为 5 的右子节点
得到的一种合法结果：
0
/ \
-10 5
\ \
-3 9
这棵树既满足二叉搜索树性质，也满足高度平衡要求。
正确性证明
结论 1：递归构造出的树满足二叉搜索树性质
在每个递归区间 [left, right] 中，算法选择中点 mid 作为根节点。由于 nums 严格递增，mid 左侧所有元素都小于 nums[mid]，mid 右侧所有元素都大于 nums[mid]。
递归构造左子树和右子树时，同样保持这个性质。因此每个节点都满足左子树节点值小于自身、右子树节点值大于自身。
所以构造出的树是二叉搜索树。
结论 2：递归构造出的树是高度平衡的
算法每次都选择当前区间的中点作为根节点，因此左右两个子区间的长度最多相差 1。
递归构造后，每个节点的左右子树都是由规模接近的两个区间构造出来的，所以左右子树高度差不会超过 1。
因此构造出的树是高度平衡二叉树。
得出结论
算法构造出的树同时满足：
- 是一棵二叉搜索树。
- 是一棵高度平衡二叉树。
- 包含数组
nums中的全部元素，且每个元素恰好使用一次。
因此算法正确。
复杂度分析
设 n 为数组 nums 的长度。
-
时间复杂度：
O(n)
每个元素都会被创建为一个树节点，且只处理一次。 -
空间复杂度：
O(log n)
递归调用栈的深度等于树高。由于构造的是平衡树，树高为O(log n)。如果不计递归栈和返回的树节点，额外空间为O(log n)。