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

题目链接

解题思路：这里面有一个构造「平衡二叉树」，似乎很难。实际上，我们每次构造时都拿中点划分，就能得到平衡的。

• 具体来说process(nums, L, R)在nums[L, R]上构造平衡搜索二叉树，我们以中点mid=(R+L)/2是头，然后左节点process(nums, L, mid - 1)，右节点process(nums, mid + 1, R)

代码

class Solution:

    def process(self, nums: List[int], L: int, R: int) -> Optional[TreeNode]:
        if L > R:
            return None
        if L == R:
            return TreeNode(nums[L])
        mid = int((R + L) / 2)
        head = TreeNode(nums[mid])
        left_head = self.process(nums, L, mid - 1)
        right_head = self.process(nums, mid + 1, R)
        head.left = left_head
        head.right = right_head
        return head


    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        return self.process(nums, 0, len(nums) -1)