LeetCode 108 [Convert Sorted Array to Binary Search Tree]

原题

给一个排序数组（从小到大），将其转换为一棵高度最小的排序二叉树。

样例
给出数组 [1,2,3,4,5,6,7], 返回

     4
   /   \
  2     6
 / \    / \
1   3  5   7

解题思路

• 根据排序数组构建查找二叉树，分治的思想，每次向下递归构建左右子树
• 时间复杂度O(n) 可以简单想每个元素被访问到了几次
• 空间复杂度O(logn) 递归的栈的大小
• 相似题目Convert Sorted List to Binary Search Tree

完整代码

# 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 nums:
            return self.buildTree(nums, 0, len(nums) - 1)
        return None
        
    def buildTree(self, nums, start, end):
        if start > end:
            return None
        root = TreeNode(nums[(start + end) / 2])
        root.left = self.buildTree(nums, start, (start + end) / 2 - 1)
        root.right = self.buildTree(nums, (start + end) / 2 + 1, end)
        return root