108. Convert Sorted Array to Binary Search Tree


Given a sorted array, the middle value could be used as the root value of the binary search tree. And its left could be used to construct the left subtree. The right subtree is also like this.


class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        return self._helper(nums, 0, len(nums))

    def _helper(self, nums, lo, hi):
        if lo == hi:
            return None
        mid = (lo + hi) // 2
        node = TreeNode(nums[mid])
        node.left = self._helper(nums, lo, mid)
        node.right = self._helper(nums, mid + 1, hi)
        return node


  • Created: 2020-01-09 23:12:52

  • Last Motified: 2020-01-09 23:12:52

  • Tags: Tree, Depth-first Search