原題
給一個排序數(shù)組（從小到大），將其轉(zhuǎn)換為一棵高度最小的排序二叉樹袒哥。
樣例
給出數(shù)組 [1,2,3,4,5,6,7], 返回
4
/ \
2 6
/ \ / \
1 3 5 7
解題思路
- 根據(jù)排序數(shù)組構(gòu)建查找二叉樹，分治的思想，每次向下遞歸構(gòu)建左右子樹
- 時間復雜度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
