难度: Easy
给你一个整数数组 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 按 严格递增 顺序排列运行时间: 80 ms
内存: 15.8 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums:
return None
lo = 0
hi = len(nums) - 1
mid = (lo + hi) // 2
node = TreeNode(nums[mid])
node.left = self.sortedArrayToBST(nums[:mid])
node.right = self.sortedArrayToBST(nums[mid+1:])
return node
这个题解使用了递归的方法来将有序数组转换为平衡二叉搜索树。主要思路是： 1. 如果数组为空，返回None。 2. 确定数组的中间元素作为当前子树的根节点。 3. 递归地将数组的左半部分转换为左子树，将右半部分转换为右子树。 4. 返回构建好的根节点。 通过选择数组的中间元素作为根节点，可以保证左右子树的节点数量尽可能平衡，从而构建出平衡二叉搜索树。
时间复杂度: O(n * log n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums:
return None
# 确定数组的中间位置
lo = 0
hi = len(nums) - 1
mid = (lo + hi) // 2
# 创建根节点
node = TreeNode(nums[mid])
# 递归构建左子树
node.left = self.sortedArrayToBST(nums[:mid])
# 递归构建右子树
node.right = self.sortedArrayToBST(nums[mid+1:])
return node
选择数组的中间元素作为根节点有利于保证左右子树包含的节点数量尽可能相等。这样可以帮助确保树的深度尽可能小，从而减少搜索时间。二叉搜索树的性能很大程度上依赖于树的高度，平衡的二叉搜索树可以保证在最坏情况下操作的复杂度接近O(log n)，其中n是树中的节点数。因此，通过选择中间元素作为根，可以最大化地减少树的不平衡情况，提高树的操作效率。
虽然在上述题解中通过分割数组来递归构建左右子树，这种方法简单直观，但每次分割数组都会产生新的数组，这会导致额外的空间和时间开销。一个更高效的方法是使用数组的索引来控制子数组的范围，而不是实际分割数组。通过传递当前子数组的起始和结束索引到递归调用中，可以避免数组的复制，从而减少空间复杂度并提高整体效率。
如果数组长度为偶数，可以选择中间两个元素中的任一个作为根节点。具体来说，可以选择中间偏左或偏右的元素。选择不同的中间元素会影响子树的大小，可能导致一边的子树比另一边多一个元素。虽然这种差异对树的平衡有一定影响，但只要不是极端的不平衡，对树的整体性能影响不大。在实际应用中，可以根据具体需求选择不同的策略，如优先保持左子树较小等。
如果输入数组不完全有序，那么构建出的二叉搜索树可能不满足二叉搜索树的性质，即对于任何一个节点，其左子树的所有节点的值都应小于该节点的值，右子树的所有节点的值都应大于该节点的值。这会影响树的搜索效率和正确性。如果数组中存在重复元素，构建的二叉搜索树可能会有多个相同的值。在二叉搜索树中，通常假设树中不包含重复元素，因此重复值的存在可能会导致树操作的预期行为发生变化，如插入、删除等操作可能需要额外的逻辑来处理重复值。