05_将有序数组转换为二叉搜索树

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


class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if not nums:
            return None
        mid = len(nums)//2
        node = TreeNode(nums[mid])
        left_nums = nums[:mid]
        right_nums = nums[mid+1:]
        node.left = self.sortedArrayToBST(left_nums)
        node.right = self.sortedArrayToBST(right_nums)
        return node




class Solution2(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if not nums:
            return None

        result = []
        mid = len(nums)//2
        i = 1
        while mid >= i:
            if i > 0:
                result.append(nums[mid-i])
            if mid + i < len(nums):
                result.append(nums[mid+i])
            i += 1

        node = TreeNode(nums[mid])

        for index, val in enumerate(result):
            if index == 0:
                node.left = TreeNode(val)
                left = node.left
                continue
            if index == 1:
                node.right = TreeNode(val)
                right = node.right
                continue
            if index % 2 == 0:
                left.left = TreeNode(val)
                left = left.left
            else:
                right.right = TreeNode(val)
                right = right.right

        return node


# a = TreeNode(0)
# b = TreeNode(-3)
# c = TreeNode(9)
# d = TreeNode(-10)
# e = TreeNode(5)
# a.left, a.right = b, c
# b.left, b.right = d, None
# c.left, c.right = e, None
nums = [-10,-3,0,5,9]
s = Solution()
print(s.sortedArrayToBST(nums))