Given an array where elements are sorted in ascending order, convert it to a height balanced BST.For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted array: [-10,-3,0,5,9],One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0 / \ -3 9 / / -10 5 思路
根据题目的意思我们需要根据有序数组来构建一个平衡二叉树，并且要满足平衡二叉树的定义。这个题我们可以使用分而治之的思想来解决。就是每次将数组分成两部分左边是左子树的部分，右边是右子树的部分。依次划分，知道数组划分完毕。代码的话最好使用递归来进行解决。 另外，leetcode上还有一道和这道类似的，只不过另外一道中是链表而不是数组。其实这道题我们可以先将链表中的数字存储到数组中，然后按照上面的办法来构建二叉树，单数如果不使用辅助空间的话，解决相对于数组就麻烦一些，每次都需要求链表的中间节点来进行不断的遍历。依次反复。 解决代码
1 # Definition for a binary tree node. 2 # class TreeNode(object): 3 # def __init__(self, x): 4 # self.val = x 5 # self.left = None 6 # self.right = None 7 8 class Solution(object): 9 def sortedArrayToBST(self, nums):10 """11 :type nums: List[int]12 :rtype: TreeNode13 """14 if not nums: # 数组为空直接返回None15 return None16 if len(nums) == 1: # 当数组中只有一个数据时返回构造的节点17 return TreeNode(nums[0])18 mid = len(nums) // 2 #去数值的中间值19 root = TreeNode(nums[mid]) # 根据中间值构造节点20 root.left = self.sortedArrayToBST(nums[:mid]) # 左子树的节点21 root.right = self.sortedArrayToBST(nums[mid+1:]) # 右子树的节点22 return root # 返回当前节点