026-力扣刷题-108--将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。(最深的深度和最浅的深度不能超过1)

示例: image.png 应该注意的是这里是可能的答案,这里的这个答案并不是唯一的

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 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
        """
        def to_bst(nums,start,end):  #定义一个递归的函数,传递进来的是原始的数组,以及起始跟终止的位置
            if start > end:  #当这个strat>end的时候就返回空,比如这里的mid跟start想等的时候,就直接返回空,意味着这个节点是空的就好了
                return None
            mid = (start+end) // 2 #因为要求是高度平衡的二叉树,因此两边树的元素的个数相差不能超过1,我们就取中间值作为每一个根节点
            node =TreeNode(nums[mid]) #存储这个节点的值
            node.left=to_bst(nums,start,mid-1)  #递归存储左孩子
            node.right=to_bst(nums,mid+1,end) #递归存储右孩子
            return node  #返回这个节点
        return to_bst(nums,0,len(nums)-1)  #整个的递归调用,返回我们想要的数组
        # print (node)