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

类型：树

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

  https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/

  ❓ 将一个升序整数数组 nums 转换为一棵平衡二叉搜索树（每个节点的左右两个子树的高度差的绝对值不超过 1）。

  💡 取中间结点

  我们选择中间元素作为树的根节点，以使树保持平衡。如果数组长度是奇数，则根节点的选择是唯一的，如果数组长度是偶数，则选取中间位置左边、右边或任选其一。

  class Solution:
      def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
          def helper(left, right):
              if left > right:
                  return None
  
              # 总是选择中间位置右边的数字作为根节点
              mid = (left + right + 1) // 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)

  时间复杂度：O(N)，空间复杂度：O(logN)