题目链接

题目描述

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例

108.jpg

示例1：

输入：nums = [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5] 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

108-2.jpg

提示

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

  • nums 按 严格递增 顺序排列

    思路

    中序遍历

    要求高度平衡，因此我们需要将根节点建立在数组的中间（这个的正确性是可以证明的，有时间补充上），根据数组大小的奇偶性，可能有多种答案。

    题解

    1. # Definition for a binary tree node.
    2. # class TreeNode:
    3. #     def __init__(self, val=0, left=None, right=None):
    4. #         self.val = val
    5. #         self.left = left
    6. #         self.right = right
    7. class Solution:
    8.   def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
    9.       def built(left, right):
    10.           if left > right:
    11.               return None
    12.           mid = (left+right)//2
    13.           root = TreeNode(nums[mid])
    14.           root.left = built(left, mid-1)
    15.           root.right = built(mid+1, right)
    16.           return root
    18.       return built(0, len(nums)-1)

    复杂度分析

  • 时间复杂度：0108-将有序数组转换为二叉搜索树 - 图3

  • 空间复杂度：0108-将有序数组转换为二叉搜索树 - 图4，递归栈的深度。