题解 | #将升序数组转化为平衡二叉搜索树#

将升序数组转化为平衡二叉搜索树

描述 给定一个升序排序的数组，将其转化为平衡二叉搜索树（BST）.

平衡二叉搜索树指树上每个节点 node 都满足左子树中所有节点的的值都小于 node 的值，右子树中所有节点的值都大于 node 的值，并且左右子树的节点数量之差不大于1

数据范围：0≤n≤10000，数组中每个值满足 ∣val∣≤5000 进阶：空间复杂度 O(n) ，时间复杂度 O(n)

思路：题目很简单，因为这个数组是升序的，既然是升序的，那么就可以直接精准的找到中间节点设为根节点，然后用递归构建左子树和右子树即可。

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return TreeNode类
#
class Solution:
    def sortedArrayToBST(self , num: List[int]) -> TreeNode:
        # write code here
        if num == None:
            return None
        n =len(num)
        if  n == 0:
            return None
        k = n//2
        T = TreeNode(num[k])
        if n == 1:
            return T
        T.left = self.sortedArrayToBST(num[:k])
        T.right = self.sortedArrayToBST(num[k+1:])
        return T