题目

难度：★☆☆☆☆
类型：二叉树

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

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

示例

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

解答

将排序数组转换为二叉搜索树，可以通过递归实现：

1. 如果函数输入为空，直接返回None；

2. 找到数组中点，将数组划分为（左半部分-中点-右半部分）三部分，中点处的值为当前树根节点的值，而当前树的左右子树根据左半部分和右半部分的数组建立，建立方式调用本函数进行递归即可；

3. 返回建立好的树。

class Solution(object):
    def sortedArrayToBST(self, nums):

        def SA2BST(nums):                                                       # 将排序数组转换为二叉搜索树
            if not nums:                                                        # 如果输入数组为空
                return None                                                     # 直接返回空
            l, r = 0, len(nums) - 1                                             # 数组左右端点位置
            mid = r // 2                                                        # 数组中点位置
            root = TreeNode(nums[mid])                                          # 根节点的值是中点处的数
            root.left, root.right = SA2BST(nums[0:mid]), SA2BST(nums[mid+1:])   # 根节点的左右孩子树通过本函数建立
            return root

        return SA2BST(nums)                                                     # 调用本函数

如有疑问或建议，欢迎评论区留言~