108. Convert Sorted Array to Binary Search Tree

Intuition

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.

Solution

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

Information

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

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

  • Tags: Tree, Depth-first Search