难度: Easy
给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。
示例:给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
Submission
运行时间: 27 ms
内存: 17.9 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:
def dfs(i,j):
if i>j:
return None
mid=(i+j)//2
node=TreeNode(nums[mid])
node.left=dfs(i,mid-1)
node.right=dfs(mid+1,j)
return node
return dfs(0,len(nums)-1)
Explain
题解采用了递归的方法来构建一棵高度平衡的二叉搜索树。首先，选取数组的中间元素作为树的根节点，这样可以保证左右子树的元素数量尽可能相等，从而达到最小高度的目的。接着，递归地使用中间元素左侧的子数组构造左子树，使用右侧的子数组构造右子树。这种方法每次都平分数组，故可以确保生成的二叉搜索树是高度平衡的。
时间复杂度: O(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:
def dfs(i, j):
if i > j:
return None # 当子数组为空时，返回None
mid = (i + j) // 2 # 找到中间元素的索引
node = TreeNode(nums[mid]) # 创建以中间元素为值的树节点
node.left = dfs(i, mid-1) # 递归构建左子树
node.right = dfs(mid+1, j) # 递归构建右子树
return node # 返回构建的树的根节点
return dfs(0, len(nums) - 1) # 从整个数组范围开始递归
Explore
选择数组的中间元素作为树的根节点可以保证左右子树的元素数量大致相等。这种平衡是非常关键的，因为在二叉搜索树中，平衡的树结构可以大大降低树的最大高度，从而使树的查找、插入和删除操作尽可能高效。如果树高度不平衡，可能会导致操作效率降低，接近于线性查找。因此，通过始终选择中间元素作为根，可以使得生成的二叉搜索树尽可能接近完全平衡，从而实现最小高度。
在数组长度为偶数时，可以选择中间两个元素中的任一个作为根节点。通常，选择中间位置的元素策略有一定的灵活性。在题解中的实现，使用`(i + j) // 2`自然地选取了中间靠左的元素作为根节点（当索引从0开始时）。这种选择仍然能够保持树的平衡性，尽管左右子树的元素数量可能相差一个。选择哪个中间元素主要取决于具体实现，但对树的总体平衡性影响不大。
递归函数`dfs`会在其输入的子数组范围无效（即`i > j`）时返回`None`。这种情况发生在尝试构建一个为空的子树时，例如，当某个节点成为叶子节点时，它的子树（左或右）可能不包含任何元素。这个返回值`None`表示在当前位置没有更多的子节点要添加，是构建正确二叉搜索树的必要步骤，确保了树的结构正确性和逻辑一致性。