原题
给一个排序数组（从小到大），将其转换为一棵高度最小的排序二叉树。
样例
给出数组 [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
