108. 将有序数组转换为二叉搜索树

• 给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵 平衡二叉搜索树。
• 思路:(递归法, 寻找根节点类似于二分查找)
  1. 选择中间元素：每次递归选择当前数组区间的中间元素作为根节点。
  2. 递归构建左右子树：递归地使用数组的左半部分构建左子树，使用右半部分构建右子树。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def sortedArrayToBST(self, nums):""":type nums: List[int]:rtype: Optional[TreeNode]"""if not nums:return Nonedef create(left, right):# 如果左边界大于右边界，说明当前区间没有元素，返回 Noneif left > right:return None# 计算当前区间的中间元素的索引mid = (left + right) // 2# 创建当前中间元素作为根节点root = TreeNode(nums[mid])# 递归地构建左子树：考虑当前区间的左半部分(left~mid-1)root.left = helper(left, mid - 1)# 递归地构建右子树：考虑当前区间的右半部分(mid+1~right)root.right = helper(mid + 1, right)# 返回构建好的根节点return root# 调用create函数，从数组的第一个元素到最后一个元素来构建平衡二叉搜索树return create(0, len(nums) - 1)

• 时间复杂度: O(n)
• 空间复杂度: O(n) , 其中，O(log n) 是递归栈的空间，O(n) 是存储树节点所需的空间