问题描述:
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9], 一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树: 0
/ \
-3 9
/ /
-10 5
思路:由于数组是有序数组,所以只需用二分法构造即可,mid即为根节点,0:mid 的中间点为左子树的根节点,mid+1:末尾的中间点为右子树的根节点,递归的构造即可。
方法1:
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if nums:
midPos = len(nums) // 2
mid = nums[midPos]
root = TreeNode(mid)
root.left = self.sortedArrayToBST(nums[:midPos])
root.right = self.sortedArrayToBST(nums[midPos+1:])
return root
2018-09-09 16:00:01