LC 108将有序数组转换为二叉搜索树Convert Sorted Array to Binary Search Tree　简单

用升序数组构建一棵高度平衡的二叉搜索树。

思路 递归取区间中点为根，左半建左子树、右半建右子树。时间 O(n)。

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