力扣刷题（第二十二天）
灵感来源
- 保持更新，努力学习
- python脚本学习
将有序数组转换为二叉搜索树
解题思路
-
选择中间节点
由于数组已排序，中间元素作为根节点可保证左右子树节点数相近。若数组长度为偶数，可选择中间左边或右边元素。 -
递归构建子树
将数组分为左半部分和右半部分，分别递归构建左子树和右子树。递归终止条件是子数组为空（即左边界超过右边界）。 -
时间复杂度与空间复杂度
- 时间复杂度：O(n)，每个元素仅访问一次。
- 空间复杂度：O(log n)，递归栈深度与树高度一致。
-
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef sortedArrayToBST(nums):def helper(left, right):if left > right:return Nonemid = (left + right) // 2root = TreeNode(nums[mid])root.left = helper(left, mid - 1)root.right = helper(mid + 1, right)return rootreturn helper(0, len(nums) - 1)
逐行解释
class TreeNode:# 定义二叉搜索树的节点结构def __init__(self, val=0, left=None, right=None):self.val = val # 当前节点存储的值self.left = left # 指向左子节点的指针self.right = right # 指向右子节点的指针def sortedArrayToBST(nums):# 将有序数组转换为高度平衡的二叉搜索树# 输入：有序数组 nums# 输出：二叉搜索树的根节点def helper(left, right):# 辅助递归函数，用于构建指定索引范围内的二叉搜索树# 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# 从整个数组范围开始构建二叉搜索树return helper(0, len(nums) - 1)