108. 将有序数组转换为二叉搜索树
题目描述
输入一个严格递增的整数数组 nums。用数组中的全部元素构造一棵二叉搜索树，并且这棵树要高度平衡。
高度平衡指：对树中每个节点，它左右两棵子树的高度相差不超过 1。
满足条件的树可能有多种，返回其中任意一种的根节点即可。返回的树按层序数组表示，null 代表空位。
示例 1
输入：nums = [-10,-3,0,5,9] 输出：[0,-10,5,null,-3,null,9]
解释：以中间元素 0 为根，左右两半分别递归建树；这只是合法答案之一。
示例 2
输入：nums = [1,3] 输出：[1,null,3]
解释：1 为根、3 为右孩子，高度差为 1，符合要求；以 3 为根也可以。
数据范围
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums严格递增。
解题思路
在闭区间内选向下取整的中点作为根，递归构造左右区间。
为什么正确
每棵子树覆盖一个连续有序区间，左右规模之差不超过一。
复杂度分析
时间 O(n)，递归栈 O(log n)，输出节点 O(n)。使用索引范围，无 Python 切片复制；若改用 nums[:mid] 等切片，每次复制 O(k) 个元素，此平衡递归的总时间将增为 O(n log n)，峰值切片辅助空间为 O(n)。
易错点
平衡树答案不唯一；示例必须与代码的中点取整规则一致。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def sortedArrayToBST(self, nums):
def build(lo, hi):
if lo > hi:
return None
mid = (lo + hi) // 2
root = TreeNode(nums[mid])
root.left = build(lo, mid - 1)
root.right = build(mid + 1, hi)
return root
return build(0, len(nums) - 1)class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return build(nums, 0, nums.length - 1);
}
private TreeNode build(int[] nums, int lo, int hi) {
if (lo > hi)
return null;
int mid = (lo + hi) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = build(nums, lo, mid - 1);
root.right = build(nums, mid + 1, hi);
return root;
}
}class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
function<TreeNode*(int, int)> build = [&](int lo, int hi) -> TreeNode* {
if (lo > hi)
return nullptr;
int mid = (lo + hi) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = build(lo, mid - 1);
root->right = build(mid + 1, hi);
return root;
};
return build(0, nums.size() - 1);
}
};func sortedArrayToBST(nums []int) *TreeNode {
var build func(lo, hi int) *TreeNode
build = func(lo, hi int) *TreeNode {
if lo > hi {
return nil
}
mid := (lo + hi) / 2
root := &TreeNode{Val: nums[mid]}
root.Left = build(lo, mid-1)
root.Right = build(mid+1, hi)
return root
}
return build(0, len(nums)-1)
}var sortedArrayToBST = function(nums) {
const build = (lo, hi) => {
if (lo > hi)
return null;
const mid = (lo + hi) >> 1;
const root = new TreeNode(nums[mid]);
root.left = build(lo, mid - 1);
root.right = build(mid + 1, hi);
return root;
};
return build(0, nums.length - 1);
};function sortedArrayToBST(nums: number[]): TreeNode | null {
const build = (lo: number, hi: number): TreeNode | null => {
if (lo > hi)
return null;
const mid = (lo + hi) >> 1;
const root = new TreeNode(nums[mid]);
root.left = build(lo, mid - 1);
root.right = build(mid + 1, hi);
return root;
};
return build(0, nums.length - 1);
};