力扣刷题（第二十二天）

灵感来源 

- 保持更新，努力学习

- python脚本学习

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

解题思路​​

1. ​​选择中间节点​​
   由于数组已排序，​​中间元素​​作为根节点可保证左右子树节点数相近。若数组长度为偶数，可选择中间左边或右边元素。

2. ​​递归构建子树​​
   将数组分为左半部分和右半部分，分别递归构建左子树和右子树。递归终止条件是子数组为空（即左边界超过右边界）。

3. ​​时间复杂度与空间复杂度​​

   • ​​时间复杂度​​：O(n)，每个元素仅访问一次。
   • ​​空间复杂度​​：O(log n)，递归栈深度与树高度一致。

1. class TreeNode:
       def __init__(self, val=0, left=None, right=None):
           self.val = val
           self.left = left
           self.right = right
   
   def sortedArrayToBST(nums):
       def helper(left, right):
           if left > right:
               return None
           mid = (left + right) // 2
           root = TreeNode(nums[mid])
           root.left = helper(left, mid - 1)
           root.right = helper(mid + 1, right)
           return root
       return 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: 当前子树在数组中的右边界索引
        
        # 递归终止条件：当左边界索引大于右边界索引时
        # 表示当前子树为空，返回 None
        if 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)