108. Convert Sorted Array to Binary Search Tree

Information

  • Diffculty: Easy

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

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

  • Tags: Tree, Depth-first Search

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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