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

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵
平衡 二叉搜索树。

平衡 二叉搜索树：任意节点的两棵子树的高度差不超过 1 而且左子树中所有节点的值 < 根节点的值；右子树中所有节点的值 > 根节点的值；其左、右子树也分别为二叉搜索树。

既然题目里面已经给出了升序排列的数组，那么我们可以直接取中间的元素作为根节点，然后递归的构建左右子树即可。这样能够保证高度差不超过1。同时，由于数组是升序的，所以左子树的元素一定比根节点小，右子树的元素一定比根节点大。

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        def construct_tree(left, right):
            if left > right:
                return None
            mid = (left + right) // 2
            root = TreeNode(nums[mid])
            root.left = construct_tree(left, mid-1)
            root.right = construct_tree(mid+1, right)
            return root
        return construct_tree(0, len(nums)-1)