- 标签:树、二叉搜索树、数组、分治、二叉树
- 难度:简单
描述:给定一个升序的有序数组 nums
。
要求:将其转换为一棵高度平衡的二叉搜索树。
说明:
-
$1 \le nums.length \le 10^4$ 。 -
$-10^4 \le nums[i] \le 10^4$ 。 -
nums
按严格递增顺序排列。
示例:
- 示例 1:
输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案
- 示例 2:
输入:nums = [1,3]
输出:[3,1]
解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
直观上,如果把数组的中间元素当做根,那么数组左侧元素都小于根节点,右侧元素都大于根节点,且左右两侧元素个数相同,或最多相差
所以猜想出:如果左右子树越平均,树就越平衡。这样我们就可以每次取中间元素作为当前的根节点,两侧的元素作为左右子树递归建树,左侧区间
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def build(left, right):
if left > right:
return
mid = left + (right - left) // 2
root = TreeNode(nums[mid])
root.left = build(left, mid - 1)
root.right = build(mid + 1, right)
return root
return build(0, len(nums) - 1)
-
时间复杂度:$O(n)$。其中
$n$ 是数组的长度。 - 空间复杂度:$O(n)$。