0108. 将有序数组转换为二叉搜索树 #
- 标签:树、深度优先搜索
- 难度:简单
题目大意 #
描述:给定一个升序的有序数组 nums
。
要求:将其转换为一棵高度平衡的二叉搜索树。
说明:
- $1 \le nums.length \le 10^4$。
- $-10^4 \le nums[i] \le 10^4$。
nums
按严格递增顺序排列。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:递归遍历 #
直观上,如果把数组的中间元素当做根,那么数组左侧元素都小于根节点,右侧元素都大于根节点,且左右两侧元素个数相同,或最多相差 $1$ 个。那么构建的树高度差也不会超过 $1$。
所以猜想出:如果左右子树越平均,树就越平衡。这样我们就可以每次取中间元素作为当前的根节点,两侧的元素作为左右子树递归建树,左侧区间 $[L, mid - 1]$ 作为左子树,右侧区间 $[mid + 1, R]$ 作为右子树。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。其中 $n$ 是数组的长度。
- 空间复杂度:$O(n)$。