E-108. Convert Sorted Array to Binary Search Tree

Loading...LeetCode

# O(n),O(n). 总体思路就是分治, 在初始nums找到中间点, 然后分为左右两个部分, 左边部分是左子树,
# 右边部分是右子树, 然后再在左右子树中进行同样的操作. 注意退出条件是右边界小于左边界
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def helper(left, right):
            mid = (right + left) // 2
          # 下面这两行可有可无
          # if right == left:
          #     return TreeNode(nums[mid])
            if right < left:
                return None
            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root
            
        return helper(0,len(nums)-1)